## 题目描述

Two kittens, Max and Min, play with a pair of non-negative integers $x$ and $y$. As you can guess from their names, kitten Max loves to maximize and kitten Min loves to minimize. As part of this game Min wants to make sure that both numbers, $x$ and $y$ became negative at the same time, and kitten Max tries to prevent him from doing so.
Each kitten has a set of pairs of integers available to it. Kitten Max has $n$ pairs of non-negative integers $(a_i, b_i)$, and kitten Min has $m$ pairs of non-negative integers $(c_j, d_j)$. As kitten Max makes a move, it can take any available pair $(a_i, b_i)$ and add $a_i$ to $x$ and $b_i$ to $y$, and kitten Min can take any available pair $(c_j, d_j)$ and subtract $c_j$ from $x$ and $d_j$ from $y$. Each kitten can use each pair multiple times during distinct moves.
Max moves first. Kitten Min is winning if at some moment both numbers $a, b$ are negative simultaneously. Otherwise, the winner of the game is kitten Max. Determine which kitten wins if both of them play optimally.

## 算法分析

\begin{align} &\exists (a, b), \; a, b \ge 0 \land a+b \gt 0, \\ &\exists (a_i, b_i), \; \forall (c_j, d_j), \; ((a_i, b_i), (a, b)) \ge ((c_j, d_j), (a, b)) \end{align}

$\because$初始时$((x, y), (a, b))=ax+by \gt 0$
$((a_i-c_j, b_i-d_j), (a, b))=((a_i, b_i), (a, b))-((c_j, d_j), (a, b)) \ge 0$
$\therefore$在任意时刻$((x’, y’), (a, b)) \gt 0$
$\therefore x’, y’$不全为负数

$$\exists (c_j, d_j), \; (a_i, b_i) \parallel (c_j, d_j) \land |(a_i, b_i)| \lt |(c_j, d_j)|$$

## 代码

#include <vector>
#include <cstdio>
#include <algorithm>

#define int long long

typedef const int ci;

inline int max(ci &a, ci &b) {
return a > b ? a : b;
}

static ci N = 100005;
int st[N << 1];
std :: vector <int> rec;
struct Point {
int type, x, y;
Point(ci &_x = 0, ci &_y = 0) : type(0), x(_x), y(_y) {}
bool operator == (const Point &p) const {
return type == p.type && x == p.x && y == p.y;
}
bool operator < (const Point &p) const {
return x == p.x ? y < p.y : x < p.x;
}
Point operator - (const Point &p) const {
return Point(x - p.x, y - p.y);
}
int operator * (const Point &p) const {
return x * p.y - y * p.x;
}
} p[N << 1];

signed main() {
int n, m, tot, mxa = 0, mxb = 0; scanf("%lld%lld%*d%*d", &n, &m), tot = n + m + 3;
for (int i = 0; i < n; ++ i) scanf("%lld%lld", &p[i].x, &p[i].y), p[i].type = 1;
for (int i = n; i < n + m; ++ i) scanf("%lld%lld", &p[i].x, &p[i].y), p[i].type = 2, mxa = max(mxa, p[i].x), mxb = max(mxb, p[i].y);
p[n + m] = Point(0, 0), p[n + m + 1] = Point(mxa, 0), p[n + m + 2] = Point(0, mxb), std :: sort(p, p + tot);
for (int i = 0, j; i < tot; i = j) {
j = i; int rec = 0;
while (j < tot && p[i].x == p[j].x && p[i].y == p[j].y) ++ j;
for (int k = i; k < j; ++ k) rec |= p[k].type;
if (rec & 1) for (int k = i; k < j; ++ k) p[k].type = 1;
}
tot = std :: unique(p, p + tot) - p;
int sz = 0;
for (int i = 0; i < tot; ++ i) {
while (sz > 1 && (p[st[sz - 1]] - p[st[sz - 2]]) * (p[i] - p[st[sz - 1]]) < 0) -- sz;
st[sz ++] = i;
}
for (int i = 0; i < sz; ++ i) rec.push_back(st[i]); sz = 0;
for (int i = tot - 1; ~ i; -- i) {
while (sz > 1 && (p[st[sz - 1]] - p[st[sz - 2]]) * (p[i] - p[st[sz - 1]]) < 0) -- sz;
st[sz ++] = i;
}
for (int i = 1; i < sz - 1; ++ i) rec.push_back(st[i]);
for (int i = rec.size() - 1; ~ i; -- i) if (p[rec[i]].type == 1) return printf("Max\n"), 0;
return printf("Min\n"), 0;
}


## 题目描述

Bessie, Farmer John’s prize cow, has just won first place in a bovine beauty contest, earning the title ‘Miss Cow World’. As a result, Bessie will make a tour of $N$ farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates $(x, y)$, each having a value in the range $-10000 \ldots 10000$. No two farms share the same pair of coordinates.
Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring. Help Bessie by computing the maximum distance among all pairs of farms.

## 代码

#include <cstdio>
#include <algorithm>

int max(int a, int b) {
return a > b ? a : b;
}

static const int N = 50005;
int st[N], rec[N];
struct Point {
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
bool operator < (const Point &p) const {
return x == p.x ? y < p.y : x < p.x;
}
Point operator - (const Point &p) const {
return Point(x - p.x, y - p.y);
}
int operator * (const Point &p) const {
return x * p.y - y * p.x;
}
int operator ! () const {
return x * x + y * y;
}
} p[N];

int main() {
int n; scanf("%d", &n);
for (int i = 0; i < n; ++ i) scanf("%d%d", &p[i].x, &p[i].y);
int top = 0, tot = 0; std :: sort(p, p + n);
for (int i = 0; i < n; ++ i) {
while (top > 1 && (p[st[top - 1]] - p[st[top - 2]]) * (p[i] - p[st[top - 2]]) <= 0) -- top;
st[top ++] = i;
}
for (int i = 0; i < top; ++ i) rec[tot ++] = st[i];
top = 0;
for (int i = n - 1; ~ i; -- i) {
while (top > 1 && (p[st[top - 1]] - p[st[top - 2]]) * (p[i] - p[st[top - 2]]) <= 0) -- top;
st[top ++] = i;
}
for (int i = 1; i < top - 1; ++ i) rec[tot ++] = st[i];
int mx = 0, pnt = 1;
for (int i = 0; i < tot; ++ i) {
int nxt = (i + 1) % tot; Point cur = p[rec[nxt]] - p[rec[i]];
while (cur * (p[rec[pnt]] - p[rec[i]]) < cur * (p[rec[(pnt + 1) % tot]] - p[rec[i]])) (++ pnt) %= tot;
mx = max(mx, max(! (p[rec[pnt]] - p[rec[i]]), ! (p[rec[pnt]] - p[rec[nxt]])));
}
printf("%d\n", mx);
return 0;
}


## 题目描述

Two of the three members of the winning team of one of the ACM regional contests are going to meet in order to train for the upcoming World Finals. They decided that they will meet sometime between $X$ o’clock and $Y$ o’clock. Because they never get anywhere on time (they were late even on the day of the regional contest), they did not set an exact time when they will meet. However, they decided that the one who gets first at the meeting point will not wait more than $Z$ minutes for the other one (they calculated that, if the other one will not come within $Z$ minutes from the arrival of the first of them, then it is very probable that he will not show up at all).
Knowing that, in the end, both of them will show up at some time between $X$ o’clock and $Y$ o’clock (not necessarily after an integer number of minutes), compute which is the probability that they will actually meet.

## 代码

#include <cstdio>

using namespace std;

struct Solver {
private:
int x, y; double z;
void input() { scanf(" %d %d %lf", &x, &y, &z); }
void process() {
int all = (y - x) * 60;
double sum = 0;
if (2 * z <= all) sum = z + 2 * (all - z) * (z / all) / 2;
else sum = z + 2 * z * (1 - z / all) / 2;
printf("%.8lf\n", sum / all);
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

Little Johnny painted on a sheet of paper a polygon with $N$ vertices. Then, for every edge of the polygon, he drew the middle point of the edge. After that, he went to school. When he came back, he found out that his brother had erased the polygon (both the edges and the vertices). The only thing left were the middle points of the edges of the polygon. Help Johnny redraw his polygon.

## 算法分析

$$\left\{ \begin{array}{c} x_1+x_2=2x_1′ \\ x_2+x_3=2x_2′ \\ \cdots \\ x_N+x_1=2x_N’ \end{array} \right.$$

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

#define random (1.0 * rand() / RAND_MAX)

using namespace std;

static const double EPS = 1e-6;
int cmp(double a, double b) {
return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1;
}

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
Point operator * (const double &n) const { return Point(x * n, y * n); }
Point operator / (const double &n) const { return *this * (1 / n); }
Point operator | (const Point &p) const { return *this + (p - *this) * 2; }
};

struct Solver {
private:
static const int N = 10010;
int n;
Point point[N];
vector <Point> ans;
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
}
void process() {
Point p;
if (n & 1) {
double sum = 0;
for (int i = 1; i <= n; ++ i) sum += point[i].x;
for (int i = 2; i <= n; i += 2) sum -= point[i].x * 2;
p.x = sum, sum = 0;
for (int i = 1; i <= n; ++ i) sum += point[i].y;
for (int i = 2; i <= n; i += 2) sum -= point[i].y * 2;
p.y = sum;
} else p = Point(random * 100000, random * 100000);
for (int i = 1; i <= n; ++ i) ans.push_back(p), p = p | point[i];
if (cmp(p.x, ans[0].x) || cmp(p.y, ans[0].y)) printf("NO\n");
else {
printf("YES\n");
for (int i = 0; i < ans.size(); ++ i) printf("%.6lf %.6lf\n", ans[i].x, ans[i].y);
}
}

public:
void solve() { input(), process(); }
} solver;

int main() {
srand(47), solver.solve();
return 0;
}


## 题目描述

The old King decided to divide the Kingdom into parts among his three sons. Each part is a polygonal area. Taking into account the bad temper of the middle son the King gave him a part of Kingdom such that moving straight from any place of this part to any other place of this part he will not cross the boundary.
There are several mineral deposits in the Kingdom. Each mineral deposit looks like a straight line segment. The middle son wants to know what part of mineral deposits is located inside his territory (not including the boundaries).

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

static const double EPS = 1e-6;
int cmp(double a, double b) { return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1; }

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {};
bool operator < (const Point &p) const { return ! cmp(x, p.x) ? cmp(y, p.y) == -1 : cmp(x, p.x) == -1; }
Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
Point operator * (const double &a) const { return Point(x * a, y * a); }
Point operator / (const double &a) const { return Point(x / a, y / a); }
double operator * (const Point &p) const { return x * p.y - y * p.x; }
double operator ! () const { return sqrt(x * x + y * y); }
};

struct Line {
Point a, b;
Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
bool operator | (const Line &l) const { return ! cmp((b - a) * (l.b - l.a), 0); }
Point operator & (const Line &l) const {
double t = (a - l.a) * (l.a - l.b) / ((a - b) * (l.a - l.b));
return a + (b - a) * t;
}
};

struct Solver {
private:
static const int N = 410;
int n, q, top;
Point point[N], sta[N];
vector <Point> poly;
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
scanf("%d", &q);
}
void init() {
sort(point + 1, point + n + 1);
for (int i = 1; i <= n; ++ i) {
while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
sta[++ top] = point[i];
}
for (int i = 1; i <= top; ++ i) poly.push_back(sta[i]); top = 0;
for (int i = n; i; -- i){
while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
sta[++ top] = point[i];
}
for (int i = 2; i < top; ++ i) poly.push_back(sta[i]);
}
bool in(Point p) {
for (int i = 0; i < poly.size(); ++ i)
if (cmp((poly[(i + 1) % poly.size()] - poly[i]) * (p - poly[i]), 0) < 0) return false;
return true;
}
void process() {
Line l;
scanf("%lf%lf%lf%lf", &l.a.x, &l.a.y, &l.b.x, &l.b.y);
for (int i = 0; i < poly.size(); ++ i) {
Line tmp(poly[i], poly[(i + 1) % poly.size()]);
if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
printf("0.00\n"); return;
}
}
vector <Point> inter;
for (int i = 0; i < poly.size(); ++ i)
if (! (Line(poly[i], poly[(i + 1) % poly.size()]) | l)) {
Line tmp = Line(poly[i], poly[(i + 1) % poly.size()]);
Point p = tmp & l;
if ((cmp(p.x, l.a.x) || cmp(p.y, l.a.y)) && (cmp(p.x, l.b.x) || cmp(p.y, l.b.y)) && cmp(min(l.a.x, l.b.x), p.x) < 1 && cmp(p.x, max(l.a.x, l.b.x)) < 1 && cmp(min(l.a.y, l.b.y), p.y) < 1 && cmp(p.y, max(l.a.y, l.b.y)) < 1 && cmp(min(tmp.a.x, tmp.b.x), p.x) < 1 && cmp(p.x, max(tmp.a.x, tmp.b.x)) < 1 && cmp(min(tmp.a.y, tmp.b.y), p.y) < 1 && cmp(p.y, max(tmp.a.y, tmp.b.y)) < 1) {
for (int j = 0; j < inter.size(); ++ j) if (! cmp(inter[j].x, p.x) && ! cmp(inter[j].y, p.y)) goto label;
inter.push_back(p);
}
label: ;
}
for (int i = 0; i < poly.size(); ++ i) {
Line tmp(poly[i], poly[(i + 1) % poly.size()]);
if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
printf("0.00\n"); return;
}
}
if (inter.empty())
if (in(l.a) && in(l.b)) printf("%.2lf\n", ! (l.b - l.a));
else printf("0.00\n");
else if (inter.size() == 2) printf("%.2lf\n", ! (inter[1] - inter[0]));
else if (in(l.a)) printf("%.2lf\n", ! (inter[0] - l.a));
else if (in(l.b)) printf("%.2lf\n", ! (inter[0] - l.b));
else printf("0.00\n");
}

public:
void solve() { input(), init(); while (q --) process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

There is a closed broken line on a plane with sides parallel to coordinate axes, without self-crossings and self-contacts. The broken line consists of $K$ segments. You have to determine, whether a given point with coordinates $(X_0, Y_0)$ is inside this closed broken line, outside or belongs to the broken line.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Line { int x1, y1, x2, y2; };

struct Solver {
private:
static const int K = 10010;
int k, x, y;
Line l[K];
void input() {
io > k;
for (int i = 1; i <= k; ++ i) {
io > l[i].x1 > l[i].y1 > l[i].x2 > l[i].y2;
if (l[i].x1 > l[i].x2 || l[i].y1 > l[i].y2) swap(l[i].x1, l[i].x2), swap(l[i].y1, l[i].y2);
}
io > x > y;
}
bool in(int x, int y, Line l) {
if (l.x1 == l.x2) return x == l.x1 && l.y1 <= y && y <= l.y2;
else return y == l.y1 && l.x1 <= x && x <= l.x2;
}
void process() {
for (int i = 1; i <= k; ++ i) if (in(x, y, l[i])) { io < (char *) "BORDER\n"; return; }
int cnt = 0;
for (int i = 1; i <= k; ++ i)
cnt += l[i].x1 == l[i].x2 && l[i].x1 > x && ((l[i].y1 <= y) ^ (l[i].y2 <= y));
if (cnt & 1) io < (char *) "INSIDE\n"; else io < (char *) "OUTSIDE\n";
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

Archipelago Ber-Islands consists of $N$ islands that are vertices of equiangular and equilateral $N$-gon. Islands are clockwise numerated. Coordinates of island $N_1$ are $(x_1, y_1)$, and island $N_2$ – $(x_2, y_2)$. Your task is to find coordinates of all $N$ islands.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

static const double PI = acos(-1);
static const double EPS = 1e-8;
int cmp(double t) { return fabs(t) < EPS ? 0 : t > 0 ? 1 : -1; }

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
Point operator * (const double &a) const { return Point(x * a, y * a); }
Point operator / (const double &a) const { return Point(x / a, y / a); }
double operator ! () const { return sqrt(x * x + y * y); }
double operator & (const Point &p) const { return x * p.x + y * p.y; }
double operator * (const Point &p) const { return x * p.y - y * p.x; }
Point operator << (const double &a) const { return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }
};

struct Solver {
private:
static const int N = 160;
int n, a, b;
Point p, q, tmp, ans[N];
void input() { scanf("%d%d%d%lf%lf%lf%lf", &n, &a, &b, &p.x, &p.y, &q.x, &q.y); }
void init() {
if (a > b) swap(a, b), swap(p, q);
double angle = 2 * PI / n * (b - a);
if (cmp(PI - angle)) {
tmp = p + (q - p) / 2 / cos((PI - angle) / 2);
tmp = (tmp - p << (angle - PI) / 2) + p;
} else tmp = p + (q - p) / 2;
}
void process() {
for (int i = 1; i <= n; ++ i)
ans[a] = p, a %= n, ++ a, p = (p - tmp << -2 * PI / n) + tmp;
for (int i = 1; i <= n; ++ i)
printf("%.6lf %.6lf\n", ans[i].x, ans[i].y);
}

public:
void solve() { input(), init(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

The mission of space explorers found on planet M the vast dungeon. One of the dungeon halls is fill with the bright spheres. The explorers find out that the light rays reflect from the surface of the spheres according the ordinary law (the incidence angle is equal to the reflectance angle, the incidence ray, the reflected ray and the perpendicular to the sphere surface lay in the one plane). The ancient legend says that if the light ray will reflect from the spheres in the proper order, than the door to the room with very precious ancient knowledge will open. You are not to guess the right sequence; your task is much simpler. You are given the positions and the radii of the spheres, the place where the laser shot was made and the direction of light propagation. And you must find out the sequence in which the light will be reflected from the spheres.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

static const long double EPS = 1e-10;
int cmp(long double t) { return fabs(t) < EPS ? 0 : t > 0 ? 1 : -1; }

struct Point {
long double x, y, z;
Point(long double _x = 0, long double _y = 0, long double _z = 0) : x(_x), y(_y), z(_z) {}
Point operator + (const Point &a) const { return Point(x + a.x, y + a.y, z + a.z); }
Point operator - (const Point &a) const { return Point(x - a.x, y - a.y, z - a.z); }
Point operator * (const long double &a) const { return Point(x * a, y * a, z * a); }
Point operator / (const long double &a) const { return Point(x / a, y / a, z / a); }
Point operator * (const Point &a) const { return Point(y * a.z - z * a.y, z * a.x - x * a.z, x * a.y - y * a.x); }
long double operator & (const Point &a) const { return x * a.x + y * a.y + z * a.z; }
long double operator ! () const { return sqrt(x * x + y * y + z * z); }
long double operator ^ (const Point &a) const { return (*this & a) / (! *this * ! a); }
};

struct Line {
Point a, b;
Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
long double operator % (const Point &p) const { return ! ((b - a) * (p - a)) / ! (b - a); }
};

struct Ball { Point p; long double r; };

struct Solver {
private:
static const int N = 50;
int n;
Point a, b;
Ball ball[N];
void input() {
cin >> n;
for (int i = 0; i < n; ++ i) cin >> ball[i].p.x >> ball[i].p.y >> ball[i].p.z >> ball[i].r;
cin >> a.x >> a.y >> a.z >> b.x >> b.y >> b.z;
}
void process() {
int p = -1, last = -1;
for (int i = 0; i < 11; ++ i) {
long double dis = 100000; p = -1;
for (int j = 0; j < n; ++ j)
if (j != last && ~ cmp((b - a) ^ (ball[j].p - a)) && ~ cmp(ball[j].r - Line(a, b) % ball[j].p)) {
long double tmp = sqrt(abs(! (ball[j].p - a) * ! (ball[j].p - a) - (Line(a, b) % ball[j].p) * (Line(a, b) % ball[j].p))) - sqrt(abs(ball[j].r * ball[j].r - (Line(a, b) % ball[j].p) * (Line(a, b) % ball[j].p)));
if (cmp(dis - tmp) == 1) dis = tmp, p = j;
}
if (! ~ p || i == 10) break; last = p;
if (i) cout << ' '; cout << p + 1;
Point c = a + (b - a) / ! (b - a) * dis;
Point d = ball[p].p + (c - ball[p].p) / ! (c - ball[p].p) * (! (a - ball[p].p) * ((a - ball[p].p) ^ (c - ball[p].p)));
b = d * 2 - a, a = c;
}
if (~ p) cout << " etc."; cout << endl;
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}



## 题目描述

Peter got a new snow blower as a New Year present. Of course, Peter decided to try it immediately. After reading the instructions he realized that it does not work like regular snow blowing machines. In order to make it work, you need to tie it to some point that it does not cover, and then switch it on. As a result it will go along a circle around this point and will remove all the snow from its path.
Formally, we assume that Peter’s machine is a polygon on a plane. Then, after the machine is switched on, it will make a circle around the point to which Peter tied it (this point lies strictly outside the polygon). That is, each of the points lying within or on the border of the polygon will move along the circular trajectory, with the center of the circle at the point to which Peter tied his machine.
Peter decided to tie his car to point $P$ and now he is wondering what is the area of the region that will be cleared from snow. Help him.

## 代码

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const long double pi = 3.1415926535898;
struct point {
long double x, y;
} p[100001];
long double x, y, ma, mi = 1e18;
long long n;
long double get_dist(int s) {
int t = s + 1;
if (t > n) t = 1;
if (p[s].x == p[t].x) return abs(p[s].x);
long double a = (p[t].y - p[s].y) / (p[t].x - p[s].x), b = -1, c = a * p[s].x - p[s].y;
return abs(c) / sqrt(a * a + b * b);
}
long double check(int s) {
int t = s + 1;
if (t > n) t = 1;
long double x1 = p[s].x, y1 = p[s].y, x2 = p[t].x, y2 = p[t].y;
long double p = x1 * (x2 - x1) + y1 * (y2 - y1), q = x2 * (x1 - x2) + y2 * (y1 - y2);
if (p < 0 && q < 0) return get_dist(s) * get_dist(s);
else if (p >= 0) return x1 * x1 + y1 * y1;
else return x2 * x2 + y2 * y2;
}
bool in() {
bool ret = false;
for (long long i = 1, j = n; i <= n; j = i++)
if (((p[i].y > y) != (p[j].y > y)) && ((p[i].x - p[j].x) * p[i].y / (p[j].y - p[i].y) + p[i].x) > 0)
ret = !ret;
return ret;
}
int main()
{
cin >> n >> x >> y;
for (int i = 1; i <= n; ++i) {
cin >> p[i].x >> p[i].y; p[i].x -= x, p[i].y -= y;
ma = max(ma, p[i].x * p[i].x + p[i].y * p[i].y);
if (i > 1) mi = min(mi, check(i - 1));
}
mi = min(mi, check(n)); if (in()) mi = 0;
cout << setprecision(10) << fixed << (ma - mi) * pi << endl;
return 0;
}