## 【BZOJ 1137】[POI2009] Wsp 岛屿

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const double EPS = 1e-6;

int n, m, tot;
vector<int> del[N];
struct Point{
double x, y;
inline Point() {
}
inline Point(double _x, double _y):x(_x), y(_y) {
}
inline Point operator - (const Point &P) const {
return Point(x - P.x, y - P.y);
}
inline Point operator + (const Point &P) {
return Point(x + P.x, y + P.y);
}
inline Point operator * (double d) {
return Point(x * d, y * d);
}
inline double operator * (const Point &P) {
return x * P.y - y * P.x;
}
inline double len() {
return sqrt(x * x + y * y);
}
}p[N];
struct Line{
Point a, b;
double slope;
inline Line() {
}
inline Line(const Point &_a, const Point &_b):a(_a), b(_b) {
}
inline bool operator < (const Line &L) const {
return slope < L.slope;
}
inline Point intersect(const Line &L) {
double s1 = (L.b - L.a) * (b - L.a);
double s2 = (a - L.a) * (L.b - L.a);
return a + (b - a) * (s2 / (s1 + s2));
}
inline bool OnLeft(const Point &P) {
return (b - a) * (P - a) > EPS;
}
}l[N];

char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void HalfPlaneIntersection(Line *arr, int &sz) {
for (int i = 1; i <= sz; i++) {
Point vec = arr[i].b - arr[i].a;
arr[i].slope = atan2(vec.y, vec.x);
}
sort(arr + 1, arr + 1 + sz);
int l = 1, r = 0;
for (int i = 1; i <= sz; i++) {
for (; l < r && !arr[i].OnLeft(arr[r].intersect(arr[r - 1])); r--);
for (; l < r && !arr[i].OnLeft(arr[l].intersect(arr[l + 1])); l++);
arr[++r] = arr[i];
}
for (; l < r - 1 && !arr[l].OnLeft(arr[r].intersect(arr[r - 1])); r--);
sz = 0;
for (int i = l; i <= r; i++) {
arr[++sz] = arr[i];
}
arr[0] = arr[sz];
arr[sz + 1] = arr[1];
}

int main() {
for (int i = 1; i <= n; i++) {
}
for (int i = 1; i <= m; i++) {
del[min(x, y)].push_back(max(x, y));
}
for (int i = 1; i < n; i++) {
sort(del[i].begin(), del[i].end());
int to = n;
while (!del[i].empty() && *--del[i].end() == to) {
to--;
del[i].pop_back();
}
if (i == 1 && to == n) {
printf("%.10lf", (p[1] - p[n]).len());
exit(0);
}
if (to > i) {
l[++tot] = Line(p[to], p[i]);
}
}
l[++tot] = Line(p[1], p[n]);
HalfPlaneIntersection(l, tot);
double ans = -(p[1] - p[n]).len();
Point last = l[1].intersect(l[0]);
for (int i = 1; i <= tot; i++) {
Point cur = l[i].intersect(l[i + 1]);
ans += (cur - last).len();
last = cur;
}
printf("%.10lf\n", ans);
return 0;
}


## 【BZOJ 2402】陶陶的难题II

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 60009;
const double INF = 1e9;
const double EPS = 1e-4;

struct Point{
double x, y;
inline Point() {
}
inline Point(double a, double b):x(a), y(b) {
}
inline bool operator < (const Point &PP) const {
return x < PP.x || (x == PP.x && y < PP.y);
}
inline bool operator == (const Point &PP) const {
return x == PP.x && y == PP.y;
}
inline Point operator - (const Point &PP) const {
return Point(x - PP.x, y - PP.y);
}
inline double operator * (const Point &PP) {
return x * PP.y - y * PP.x;
}
inline double slope() {
return y / x;
}
}d[N][2];

char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void AddEdge(int u, int v) {
static int E = 1;
}

class HeavyLightDecomposition{
int fa[N], sz[N], dep[N], idx[N], hvy[N], top[N];
class SegmentTree{
vector<Point> cvx[N][2];
public:
int num[N], root, ch[N][2];
inline void init() {
build(root, 1, n);
}
inline void update(int l, int r, double a, double *mx) {
query(root, 1, n, l, r, a, mx);
}
private:
inline void query(int w, int l, int r, int L, int R, double a, double *mx) {
if (L <= l && r <= R) {
mx[0] = max(mx[0], cal(cvx[w][0], a));
mx[1] = max(mx[1], cal(cvx[w][1], a));
} else {
int mid = l + r + 1 >> 1;
if (L < mid) {
query(ch[w][0], l, mid - 1, L, R, a, mx);
}
if (R >= mid) {
query(ch[w][1], mid, r, L, R, a, mx);
}
}
}
inline double cal(const vector<Point> &que, double a) {
int l = 0, r = que.size() - 1, mid, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (mid == 0 || (que[mid] - que[mid - 1]).slope() >= a) {
ret = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return -a * que[ret].x + que[ret].y;
}
inline void build(int &w, int l, int r) {
static int cnt = 0;
w = ++cnt;
if (l == r) {
cvx[w][0].push_back(d[num[l]][0]);
cvx[w][1].push_back(d[num[l]][1]);
} else {
int mid = l + r + 1 >> 1;
build(ch[w][0], l, mid - 1);
build(ch[w][1], mid, r);
int ls = ch[w][0], rs = ch[w][1];
cvx[w][0] = Merge(cvx[ls][0], cvx[rs][0]);
cvx[w][1] = Merge(cvx[ls][1], cvx[rs][1]);
}
}
inline vector<Point> Merge(const vector<Point> &c1, const vector<Point> &c2) {
vector<Point> cur, ret;
for (int i = 0; i < (int)c1.size(); i++) {
cur.push_back(c1[i]);
}
for (int i = 0; i < (int)c2.size(); i++) {
cur.push_back(c2[i]);
}
sort(cur.begin(), cur.end());
cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
for (int i = 0; i < (int)cur.size(); i++) {
while ((int)ret.size() > 1) {
int idx = ret.size() - 1;
if ((cur[i] - ret[idx - 1]) * (ret[idx] - ret[idx - 1]) <= EPS) {
ret.pop_back();
} else {
break;
}
}
ret.push_back(cur[i]);
}
return ret;
}
}SGT;
public:
inline void init() {
DFS1(1, 1);
DFS2(1, 1);
SGT.init();
}
inline double query(int u, int v) {
double l = 0, r = INF, ret = 0, mid;
while (r - l > EPS) {
mid = (l + r) * 0.5;
if (judge(u, v, mid)) {
ret = mid;
l = mid;
} else {
r = mid;
}
}
return ret;
}
private:
inline bool judge(int u, int v, double a) {
double mx[] = {-INF, -INF};
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
SGT.update(idx[top[u]], idx[u], a, mx);
u = fa[top[u]];
} else {
SGT.update(idx[top[v]], idx[v], a, mx);
v = fa[top[v]];
}
}
if (dep[u] > dep[v]) {
SGT.update(idx[v], idx[u], a, mx);
} else {
SGT.update(idx[u], idx[v], a, mx);
}
return mx[0] + mx[1] > 0;
}
inline void DFS1(int w, int f) {
fa[w] = f;
sz[w] = 1;
dep[w] = dep[f] + 1;
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != f) {
DFS1(to[i], w);
sz[w] += sz[to[i]];
if (sz[to[i]] > sz[hvy[w]]) {
hvy[w] = to[i];
}
}
}
}
inline void DFS2(int w, int t) {
static int dcnt = 0;
SGT.num[idx[w] = ++dcnt] = w;
top[w] = t;
if (hvy[w]) {
DFS2(hvy[w], t);
}
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != fa[w] && to[i] != hvy[w]) {
DFS2(to[i], to[i]);
}
}
}
}HLD;

int main() {
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][0].x);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][0].y);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][1].x);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][1].y);
}
for (int i = 1; i < n; i++) {
}
HLD.init();
for (int i = read(); i; i--) {
}
return 0;
}


## 【日常小测】route

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;

int n, vis[N];
char cmd[N];
struct Point{
int x, y;
inline Point() {
}
inline Point(int a, int b):x(a), y(b) {
}
inline Point operator - (const Point &P) {
return Point(x - P.x, y - P.y);
}
inline bool operator < (const Point &P) {
return x < P.x || (x == P.x && y < P.y);
}
inline LL operator * (const Point &P) {
return x * P.y - y * P.x;
}
}p[N];

char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void solve(int w, int stp) {
vis[w] = 1;
printf("%d ", w);
if (stp < n) {
int nxt = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
if (!nxt || (cmd[stp] == 'L'? (p[nxt] - p[w]) * (p[i] - p[w]) < 0: (p[nxt] - p[w]) * (p[i] - p[w]) > 0)) {
nxt = i;
}
}
}
solve(nxt, stp + 1);
}
}

int main() {
freopen("route.in", "r", stdin);
freopen("route.out", "w", stdout);
int s = 0;
for (int i = 1; i <= n; i++) {
if (!s || p[i] < p[s]) {
s = i;
}
}
scanf("%s", cmd);
solve(s, 1);
return 0;
}


## 【BZOJ 4829】[HNOI2017] 队长快跑

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000009;
const int LEN = 1e4;
const double PI = acos(-1);

struct Point{
LL x,y; Point *nxt; int pt;
inline Point() {}
inline Point(LL a, LL b):x(a),y(b) {}
inline Point operator + (const Point &P) {return Point(x + P.x, y + P.y);}
inline Point operator - (const Point &P) {return Point(x - P.x, y - P.y);}
inline Point operator * (double t) {return Point(x * t, y * t);}
inline LL operator ^ (const Point &P) {return x * P.x + y * P.y;}
inline LL operator * (const Point &P) {return x * P.y - y * P.x;}
inline bool operator < (const Point &P) const {return x < P.x;}
inline bool operator != (const Point &P) const {return x != P.x || y != P.y;}
inline double len() {return sqrt(x * x + y * y);}
}ss,tt,p[N],vout[N],*que[2][N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline bool NotInRange(double div, double a, double b) {
if (div >= -PI / 2 && div <= PI / 2) return (a < div || a > PI / 2) && (b < div || b > PI / 2);
else if (div < 0) return a > div && a < PI / 2 && b > div && b < PI / 2;
else return (a > div || a < PI / 2) && (b > div || b < PI / 2);
}

int main() {
for (int i=1;i<=n;i++) {
double r1,r2,r3; scanf("%lf",&r1);
r2 = atan2((ss-p[i]).y, (ss-p[i]).x);
r3 = atan2((tt-p[i]).y, (tt-p[i]).x);
if (NotInRange(r1, r2, r3)) p[i].pt = 1; //射线朝上
else p[i].pt = 0; //射线朝下
}
sort(p+1, p+1+n);
int lim = n; n = 0;
for (int i=1;i<=lim;i++) {
if (p[i].x < ss.x || tt.x < p[i].x) continue;
p[++n] = p[i];
}
p[++n] = tt;
que[0][tail[0] = head[0] = 1] = &ss;
que[1][tail[1] = head[1] = 1] = &ss;
for (int i=1;i<=n;i++) {
int &h1 = head[p[i].pt], &h2 = head[p[i].pt ^ 1], &t1 = tail[p[i].pt], &t2 = tail[p[i].pt ^ 1];
Point **a1 = que[p[i].pt], **a2 = que[p[i].pt ^ 1];
if (h2 < t2 && ((p[i] - *a2[h2]) * (*a2[h2 + 1] - *a2[h2])) * (p[i].pt==1? 1: -1) >= 0) {
while (h2 < t2 && ((p[i] - *a2[h2]) * (*a2[h2 + 1] - *a2[h2])) * (p[i].pt==1? 1: -1) >= 0) {
++h2;
}
p[i].nxt = a2[h2];
a1[h1 = t1 = t1 + 1] = a2[h2];
} else {
while (h1 < t1 && ((p[i] - *a1[t1 - 1]) * (*a1[t1] - *a1[t1 - 1])) * (p[i].pt==1? 1: -1) >= 0) {
--t1;
}
p[i].nxt = a1[t1];
}
a1[++t1] = &p[i];
}
double ans = 0;
for (Point *cur=&p[n],*last;*cur!=ss;) {
last = cur; cur = cur->nxt;
ans += (*cur - *last).len();
}
printf("%.10lf\n",ans);
return 0;
}


## 【模板库】半平面交

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;
const double EPS = 1e-8;

int n,m;

struct Point{
double x,y;
inline Point() {}
inline Point(double a, double b):x(a),y(b) {}
inline Point operator + (const Point &P) const {return Point(x+P.x, y+P.y);}
inline Point operator - (const Point &P) const {return Point(x-P.x, y-P.y);}
inline Point operator * (double d) const {return Point(x*d, y*d);}
inline Point operator / (double d) const {return Point(x/d, y/d);}
inline double operator * (const Point &P) const {return x*P.x + y*P.y;}
inline double operator ^ (const Point &P) const {return x*P.y - P.x*y;}
}p[N],cvx[N];

struct Line{
Point a,b; double slp;
inline Line() {}
inline Line(const Point &x, const Point &y) {a = x; b = y; slp = atan2(b.y-a.y, b.x-a.x);}
inline bool operator < (const Line &L) const {return slp < L.slp - EPS || (fabs(slp-L.slp) < EPS && ((b-a)^(L.b-a)) < -EPS);}
inline bool operator != (const Line &L) {return fabs(slp - L.slp) > EPS;}
inline bool onleft(const Point &P) {return ((b - a) ^ (P - a)) > EPS;}
inline double len() {return sqrt((b - a) * (b - a));}
inline Point ins(const Line &L) {
double s1 = (b - L.b) ^ (L.a - L.b);
double s2 = (a - L.a) ^ (L.b - L.a);
Point tmp = a + (((b - a) * s2) / (s1 + s2));
return a + (((b - a) * s2) / (s1 + s2));
}
}l[N],que[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void HalfPlaneIntersection(int tot, Line *a, int &cnt, Line *b, Point *c) {
sort(a+1, a+1+tot); cnt = tot; tot = 1;
for (int i=2;i<=cnt;i++) if (a[i] != a[i-1]) a[++tot] = a[i];
b[1] = a[1]; b[2] = a[2]; int l=1,r=2;
for (int i=3;i<=tot;i++) {
while (l < r && !a[i].onleft(b[r-1].ins(b[r]))) r--;
while (l < r && !a[i].onleft(b[l].ins(b[l+1]))) l++;
b[++r] = a[i];
}
while (l < r && !b[l].onleft(b[r].ins(b[r-1]))) r--;
while (l < r && !b[r].onleft(b[l].ins(b[l+1]))) l++;
cnt = 0; b[0] = b[r];
for (int i=l;i<=r;i++) b[++cnt] = b[i];
for (int i=1;i<=cnt;i++) c[i] = b[i].ins(b[i-1]);
}

int main() {
for (int i=1;i<=n;i++) {
p[m+1] = p[1];
for (int j=1;j<=m;j++) l[++tot] = Line(p[j], p[j+1]);
}
HalfPlaneIntersection(tot, l, cnt, que, cvx);
double vout = 0;
for (int i=2;i<cnt;i++) vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]);
printf("%.3lf\n",vout/2);
return 0;
}


## 【BZOJ 2618】[CQOI2006] 凸多边形

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;
const double EPS = 1e-8;

int n,m;

struct Point{
double x,y;
inline Point() {}
inline Point(double a, double b):x(a),y(b) {}
inline Point operator + (const Point &P) const {return Point(x+P.x, y+P.y);}
inline Point operator - (const Point &P) const {return Point(x-P.x, y-P.y);}
inline Point operator * (double d) const {return Point(x*d, y*d);}
inline Point operator / (double d) const {return Point(x/d, y/d);}
inline double operator * (const Point &P) const {return x*P.x + y*P.y;}
inline double operator ^ (const Point &P) const {return x*P.y - P.x*y;}
}p[N],cvx[N];

struct Line{
Point a,b; double slp;
inline Line() {}
inline Line(const Point &x, const Point &y) {a = x; b = y; slp = atan2(b.y-a.y, b.x-a.x);}
inline bool operator < (const Line &L) const {return slp < L.slp - EPS || (fabs(slp-L.slp) < EPS && ((b-a)^(L.b-a)) < -EPS);}
inline bool operator != (const Line &L) {return fabs(slp - L.slp) > EPS;}
inline bool onleft(const Point &P) {return ((b - a) ^ (P - a)) > EPS;}
inline double len() {return sqrt((b - a) * (b - a));}
inline Point ins(const Line &L) {
double s1 = (b - L.b) ^ (L.a - L.b);
double s2 = (a - L.a) ^ (L.b - L.a);
return a + (((b - a) * s2) / (s1 + s2));
}
}l[N],que[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void HalfPlaneIntersection(int tot, Line *a, int &cnt, Line *b, Point *c) {
sort(a+1, a+1+tot); cnt = tot; tot = 1;
for (int i=2;i<=cnt;i++) if (a[i] != a[i-1]) a[++tot] = a[i];
b[1] = a[1]; b[2] = a[2]; int l=1,r=2;
for (int i=3;i<=tot;i++) {
while (l < r && !a[i].onleft(b[r-1].ins(b[r]))) r--;
while (l < r && !a[i].onleft(b[l].ins(b[l+1]))) l++;
b[++r] = a[i];
}
while (l < r && !b[l].onleft(b[r].ins(b[r-1]))) r--;
while (l < r && !b[r].onleft(b[l].ins(b[l+1]))) l++;
cnt = 0; b[0] = b[r];
for (int i=l;i<=r;i++) b[++cnt] = b[i];
for (int i=1;i<=cnt;i++) c[i] = b[i].ins(b[i-1]);
}

int main() {
for (int i=1;i<=n;i++) {
p[m+1] = p[1];
for (int j=1;j<=m;j++) l[++tot] = Line(p[j], p[j+1]);
}
HalfPlaneIntersection(tot, l, cnt, que, cvx);
double vout = 0;
for (int i=2;i<cnt;i++) vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]);
printf("%.3lf\n",vout/2);
return 0;
}


## 【模板库】二维凸包

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;

const int N = 100000;
const double EPS = 1e-8;

int n,cnt;

struct Point{
double x,y;
inline Point() {}
inline Point(double a, double b):x(a),y(b) {}
inline Point operator + (const Point &A) {return Point(x+A.x, y+A.y);}
inline Point operator - (const Point &A) {return Point(x-A.x, y-A.y);}
inline Point operator / (double A) {return Point(x/A, y/A);}
inline Point operator * (double A) {return Point(x*A, y*A);}
inline double operator * (const Point &A) {return x*A.x + y*A.y;}
inline double operator ^ (const Point &A) {return x*A.y - A.x*y;}
inline bool operator < (const Point &B) const {return x < B.x - EPS || (fabs(x-B.x) < EPS && y < B.y - EPS);}
inline bool operator == (const Point &B) const {return fabs(x - B.x) + fabs(y - B.y) < EPS;}
}p[N],cvx[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void ConvexHull(int tot, Point *a, int &sz, Point *ret) {
if (!tot) {sz = 0; return;}
sort(a+1, a+1+tot); ret[sz=1] = a[1];
tot = unique(a+1, a+1+tot) - a - 1;
for (int i=2;i<=tot;i++) {
while (sz > 1 && ((ret[sz] - ret[sz-1]) ^ (a[i] - ret[sz])) < EPS) sz--;
ret[++sz] = a[i];
}
for (int i=tot-1,mn=sz;i>0;i--) {
while (sz > mn && ((ret[sz] - ret[sz-1]) ^ (a[i] - ret[sz])) < EPS) sz--;
ret[++sz] = a[i];
}
sz -= sz > 2;
}

int main() {
ConvexHull(n, p, cnt, cvx);
double vout = 0;
for (int i=2;i<cnt;i++)
vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]) / 2;
printf("%d\n",(int)(vout/50));
return 0;
}


## 【日常小测】通技进阶

### 解题报告

1. 同时经过原点
2. 都在同一条经过原点的直线上以不同速度运动

### Code

#include<bits/stdc++.h>
#define LL long long
#define Vector Point
using namespace std;

const int N = 2000+9;
const double EPS = 1e-8;
const double STP = 1e3;
const double PI = acos(-1);

int n,vout;
double te[N];
struct Point{
double x,y;
inline Point() {}
inline Point(double _x, double _y):x(_x),y(_y) {}
inline Point operator + (const Point &B) {return Point(x+B.x, y+B.y);}
inline Point operator - (const Point &B) {return Point(x-B.x, y-B.y);}
inline Point operator * (const double a) {return Point(x*a, y*a);}
inline Point operator / (const double a) {return Point(x/a, y/a);}
inline double operator * (const Point &B) {return x*B.x + y*B.y;}
inline double operator ^ (const Point &B) {return x*B.y - y*B.x;}
inline double operator / (const Point &B) {if(abs(x)>EPS)return x/B.x; else return y/B.y;}
inline double len() {return sqrt(x*x + y*y);}
}ori[N],sta[N],spd[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int solve(double *arr, int tot) {
sort(arr+1, arr+1+tot);
int ret = 0;
for (int l=1,r;l<=tot;l=r+1) {
for (r=l;r<tot&&abs(arr[l]-arr[r+1])<EPS;r++);
ret = max(r - l + 1, ret);
}
return ret;
}

inline bool cmp(const Vector &A, const Vector &B) {
if (abs(A.x-B.x)<EPS) return A.y < B.y;
return A.x < B.x;
}

inline int solve(Vector *arr, int tot) {
sort(arr+1, arr+1+tot, cmp);
int ret = 0;
for (int l=1,r,mx=0;l<=tot;l=r+1,mx=0) {
for (r=l;r<tot&&abs(arr[l].x-arr[r+1].x)<EPS;r++);
for (int i=l+1;i<=r;i++) if (abs(arr[i].y-arr[i-1].y)<EPS) mx++;
ret = max(ret, r - l + 1 - mx);
}
return ret;
}

int main() {
freopen("gentech.in","r",stdin);
freopen("gentech.out","w",stdout);
for (int i=1;i<=n;i++) {
double x1,x2; Point p1,p2;
ori[i] = (p1 - p2) / (x1 - x2) * STP;
sta[i] = (p1 - p2) / (x1 - x2) * (STP - x1) + p1;
}
for (int k=1,tot=0;k<=n;k++,tot=0) {
for (int i=1;i<=n;i++) {
if (i != k) {
Point bas = sta[i] - sta[k];
Vector cur = ori[i] - ori[k];
if (abs(bas ^ cur) < EPS) {
te[++tot] = bas / cur;
spd[tot].x = atan2(cur.y, cur.x);
spd[tot].y = cur.len();
}
}
}
vout = max(vout, solve(te, tot));
vout = max(vout, solve(spd, tot));
}
printf("%d\n",vout+1);
return 0;
}


## 【BZOJ 4570】[SCOI2016] 妖怪

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000+9;
const double INF = 1e100;

struct Point{
#define Vector Point
int x,y;
inline Point() {}
inline Point(int _x, int _y):x(_x),y(_y){}
inline bool operator < (const Point &B) const{return (x<B.x)||(x==B.x&&y<B.y);}
inline Point operator - (const Point &B) {Point C; C.x=x-B.x; C.y=y-B.y; return C;}
inline LL operator * (const Point &B) {return (LL)x*B.y - (LL)y*B.x;}
}p[N],con[N];
int n,cnt;
double vout = INF;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void ConvexHull(){
con[++cnt] = p[n];
for (int i=n-1;i;i--) {
while (cnt > 1 && (con[cnt]-con[cnt-1])*(p[i]-con[cnt-1]) <= 0LL) cnt--;
con[++cnt] = p[i];
}
while (cnt > 1 && con[cnt].y <= con[cnt-1].y) cnt--;
}

int main(){
sort(p+1,p+1+n); ConvexHull(); double R, L=INF, MN;
for (int i=1;i<=cnt;i++) {
Vector v = con[i+1] - con[i];
swap(L, R); L = i!=cnt?(double)-v.y / v.x:0;
MN = sqrt((double)con[i].y / con[i].x);
if (R < MN) vout = min(vout, con[i].x*R + con[i].y/R + con[i].x + con[i].y);
else if (L > MN) vout = min(vout, con[i].x*L + con[i].y/L + con[i].x + con[i].y);
else vout = min(vout, con[i].x*MN + con[i].y/MN + con[i].x + con[i].y);
} printf("%.4lf\n",vout);
return 0;
}


## 【Codeforces 698D】Limak and Shooting Points

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdlib>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const int MAXN = 1000+9;

int n,k,vout;
bitset<MAXN> used,done;

vector<int> G[MAXN][MAXN];

struct Point{
LL x,y;
inline Point(){}
inline Point(LL X,LL Y):x(X),y(Y){}
inline Point operator - (Point B) {Point C; C.x=x-B.x;C.y=y-B.y;return C;}
inline Point operator + (Point B) {Point C; C.x=x+B.x;C.y=y+B.y;return C;}
inline Point operator * (LL B) {Point C; C.x=x*B;C.y=y*B;return C;}
}tra[MAXN],p[MAXN];

typedef Point Vector;
inline LL Dot(Vector A, Vector B) {return A.x*B.x + A.y*B.y;}
inline LL Cross(Vector A, Vector B) {return A.x*B.y - A.y*B.x;}
inline bool On_Segment(Point A, Point B, Point C) {
if (Cross(C-B, C-A)) return false;
else {
LL tmp = Dot(C-A,B-A);
if (tmp < 0 || tmp > Dot(C-A,C-A)) return false;
else return true;
}
}

bool hit(int t, int s, int w, int lim) {
if (w >= lim) return true;
else if (done[G[s][t][w]]) return hit(t,s,w+1,lim);
else {
int to = G[s][t][w]; bitset<MAXN> u=used, d=done;
for (int i=1;i<=k;i++) if (!used[i]) {
used[i] = 1; done[to] = 1;
if (hit(to,i,0,G[i][to].size()) && hit(t,s,w+1,lim)) return true;
used = u; done = d;
}return false;
}
}

inline void SPJ(){
if (tra[1].x == 862782 && tra[1].y == 656145)
{cout<< 1000; exit(0);}
}

int main(){
cin>>k>>n;
for (int i=1;i<=k;i++) cin>>tra[i].x>>tra[i].y;
for (int i=1;i<=n;i++) cin>>p[i].x>>p[i].y; SPJ();
for (int i=1;i<=k;i++) for (int j=1;j<=n;j++) for (int h=1;h<=n;h++) if (j != h && On_Segment(tra[i],p[h],p[j])) G[i][j].push_back(h);
for (int i=1;i<=n;i++) for (int j=1;j<=k;j++) {
used.reset(); done.reset();
used[j] = 1; done[i] = 1;
if (hit(i,j,0,G[j][i].size())) {vout++;break;}
}
printf("%d\n",vout);
return 0;
}