【BZOJ 1137】[POI2009] Wsp 岛屿

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1137

解题报告

不难发现每一个点应尽量向编号大的点连边
所以就只剩下$O(n)$条线段了,直接做半平面交就好

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];
 
inline int read() {
    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() {
    n = read(); m = read();
    for (int i = 1; i <= n; i++) {
        p[i].x = read();
        p[i].y = read();
    }
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        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

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/20170624_problem.pdf

解题报告

我们往后多看一步:

假设下一步我们需要向左走,那么我们这一步就走到对于现在所在的点极角序最小的点去
否则就走到极角序最大的点去

不难发现这样一定能构造出一组解

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

inline int read() {
	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);
	n = read();
	int s = 0;
	for (int i = 1; i <= n; i++) {
		p[i].x = read();
		p[i].y = read();
		if (!s || p[i] < p[s]) {
			s = i;
		}
	}
	scanf("%s", cmd);
	solve(s, 1);
	return 0;
}

【BZOJ 4829】[HNOI2017] 队长快跑

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4829

解题报告

首先我们可以把每一条射线等价为一条垂直于$x$轴的射线
此时问题变成了$Flappy \ Bird$那样

然后我们发现问题就是上下两个凸包互相卡
然后用两个队列瞎搞搞就好了

另外这题精度巨坑
之前用$long double$各种判$EPS$还是挂成狗
所以建议安心用$long long$

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

int n,tot,st[N],head[2],tail[2];
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];

inline int read() {
	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() {
	n = read(); tt.x = read(); tt.y = read();
	for (int i=1;i<=n;i++) {
		p[i].x = read(); p[i].y = read();
		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;
}

【日常小测】通技进阶

相关链接

题目传送门:http://paste.ubuntu.com/23686161/

解题报告

这题好神啊!

首先这题是三维几何,大家都不是很会的样子
于是我们考虑用一个平行于y-z平面的平面A,沿着x轴扫描
于是三维的直线就变成了一个在二维平面上运动的点

现在考虑那个两两相交的边集
选定一个点为原点进行坐标变换后,其他点只会有两种情况:

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

于是暴力枚举那个点,然后sort之后搞一搞
在 \(O(nlogn)\) 的时间复杂度内就可以解决啦!

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

inline int read() {
	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);
	n = read();
	for (int i=1;i<=n;i++) {
		double x1,x2; Point p1,p2;
		x1 = read(); p1.x = read(); p1.y = read();
		x2 = read(); p2.x = read(); p2.y = read();
		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

题目传送门:http://codeforces.com/contest/699/problem/F

就是一个傻逼的暴力搜索,
但始终wa一个点,MD弃了

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