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

【BZOJ 2402】陶陶的难题II

相关链接

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

解题报告

不难发现这是一个分数规划问题
再化一化式子就可以转换成凸包上选点的问题
至于支持链上的询问我们可以套树链剖分
总的时间复杂度:$O(n \log^3 n)$

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;

int n, head[N], nxt[N], to[N];
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];

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 AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

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() {
	n = read();
	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++) {
		AddEdge(read(), read());
	}
	HLD.init();
	for (int i = read(); i; i--) {
		printf("%.10lf\n", HLD.query(read(), read()));
	}
	return 0;
}

【日常小测】route

相关链接

题目传送门:http://oi.cyo.ng/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://www.lydsy.com/JudgeOnline/problem.php?id=2618
参考资料:http://foenix.top/2015/03/17/半平面交nlogn方法小结/
备注:这份代码不能处理退化成一个点或一条线的情况,如果实在要处理这种情况,请自行将直线平移适当距离

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

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 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() {
	n = read(); int tot=0,cnt=0;
	for (int i=1;i<=n;i++) {
		m = read();
		for (int j=1;j<=m;j++) p[j].x = read(), p[j].y = read();
		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] 凸多边形

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2618
神犇题解:http://hzwer.com/4713.html

解题报告

把每一个凸多边形看成一堆半平面
于是原题变成求半平面交

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

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

【模板库】二维凸包

参考例题:http://poj.org/problem?id=3348
备注:可以处理重点,坐标值可以是整数和小数

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

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

【BZOJ 4548】小奇的糖果

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4548
神犇题解:http://www.cnblogs.com/lcf-2000/p/6204367.html

解题报告

自己做的时候怎么都只会$O(n^2)$的算法啊……
看来还是我太年轻了 QwQ

我们来枚举是哪一种颜色不在所选集合中
枚举之后问题变成选择一个不含特定颜色的矩形,使其内部的点最多
下面我们来分情况讨论这个问题:

1. 我们所选矩形没有上下边界的限制

这个我们扫一遍,顺便记录一下就可以了

2. 我们所选的矩形有上/下边界的限制

这个东西我们可以用一个水平的扫描线从上往下扫描一遍
途中需要差前驱,后继这个用平衡树就可以了(似乎这一块可以用并查集优化掉$\log$?)

然后这题就做完啦!

【BZOJ 3482】[COCI2013] hiperprostor

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3482
神犇题解:http://www.cnblogs.com/clrs97/p/4675155.html

解题报告

我们发现一条路径的长度为$ax+b$,是一条直线的形式
那么我们如果求出所有直线的凸包,那么就可以$O(n)$计算答案了

现在考虑如何搞出凸包:

若两条直线的斜率相等,那么纵截距较小的一定优于纵截距较大的
于是我们可以定义状态$f_{i,j}$表示到达$i$点,斜率为$j$,的路径纵截距最小是多少
这个我们可以使用Dijkstra搞出来,之后我们显然可以$O(n)$构造出凸包了

有了凸包后,每一条线段的贡献就是一个等差数列,这个显然可以$O(1)$计算
于是总的时间复杂度就是$O(Qn^2 \log (n^2))$

【日常小测】通技进阶

相关链接

题目传送门: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;
}

【CodeChef NTHCIR】Rohith and Circles

题目传送门:https://www.codechef.com/problems/NTHCIR
中文题面:http://oi.cyo.ng/wp-content/uploads/2016/10/NTHCIR.pdf

这个题啊! 调试起来实在是太恶心了。
鉴于最近赶进度,就先弃疗了。
我没调过的代码:http://paste.ubuntu.com/23337455/
神犇随便写写就过了的代码:http://paste.ubuntu.com/23337458/

另外强烈安利这位神犇的题解,超级良心有木有:
http://pppfish.com/archives/1609

【算法笔记】圆的反演

先来挖坑:
例题一:http://acm.hdu.edu.cn/showproblem.php?pid=4773
题解一:http://wangzhpp.org/?p=106
例题二:https://www.codechef.com/problems/NTHCIR
题解二:http://pppfish.com/archives/1609
例题二的中文题面:http://oi.cyo.ng/wp-content/uploads/2016/10/NTHCIR.pdf

—– UPD 2016.10.17 —–
例题一的题解:http://oi.cyo.ng/?p=1738
例题二的题解:http://oi.cyo.ng/?p=1740
ps:感觉最近这么颓废,吃枣药丸

【BZOJ 4570】[SCOI2016] 妖怪

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

这个题,省选的时候思路一点没错啊!(╯‵□′)╯︵┻━┻
是我考试的时候心太急了,当然草稿纸太小绝对也是原因之一 (逃

就是推一推式子,发现是个凸包+对勾函数
于是搞一搞范围,求一求极值就可以辣!

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

题目传送门: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;
}

【算法笔记】凸包上选点问题

问题一:在凸包上,选三个点使围成的面积最大
结论:一直不停的转一转,O(n)可过
证明:YYY的不严密的反证法

问题二:在凸包上,选四个点使围成的面积最大
结论:最优解一定是由两组对踵点对构成,于是旋转卡壳卡一卡也是O(n)的
证明:可以一步步证到,一般的点,一定不是最优解,进而证到,最优解一定是由两对对踵点对构成

哎,今晚好想睡觉,先简单写写,过几天再来填坑QAQ