## 【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;
}


## 【日常小测】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;
}


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

### 解题报告

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;
}


## 【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;
}