自动搬运

查看原文

来自洛谷，原作者为

	s_r_f 这里是一个只会背板和fst的蒟蒻

搬运于2025-08-24 22:24:07，当前版本为作者最后更新于2020-08-31 18:40:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我的CEOI作战记录&题解-洛谷博客

我的CEOI作战记录&题解-cnblogs

计算几何扫描线题.

首先为了防止出现一些边界情况，(比如有一条无斜率的线段)，可以把点转一个角度。

用set维护当前的所有线段，并记录每条线段上方，最晚被插入/删除的后继的线段。

然后从左到右扫描线，

在每次加入线段的时候，考虑把加入的线段的左端点和set里的一个点连接起来。

考虑这个线段在set上的前驱，如果前驱上记录了点，那我就把这个点和记录的点连起来，否则我就和前驱这条线段的左端点连起来。 同时用当前这条线段的左端点来更新前驱记录的点。

在每次删除点的时候，更新一下set上的前驱记录的点即可。

复杂度$O(n \log n).$

代码 :

#define db long double
const int N = 100050;
db Pi = acos(-1.0),theta = Pi * (1.0 * 139 / 180),cost = cos(theta),sint = sin(theta);
struct point{
	db x,y; int realx,realy;
	inline void calc(){ x = cost * realx - sint * realy,y = cost * realy + sint * realx; }
}p[N<<1]; int n;
inline void print(point a,point b){
	cout << a.realx << ' ' << a.realy << ' ' << b.realx << ' ' << b.realy << '\n';
}
struct Event{
	int id,tp; db x;
	bool operator < (Event w) const{ return x < w.x; }
}ev[N<<1];
db T;
struct line{
	int s,t; mutable int lst; db k,b;
	inline void calc(){ k = (p[s].y - p[t].y) / (p[s].x - p[t].x),b = p[s].y - k * p[s].x; }
	bool operator < (const line w) const{ return k*T+b < w.k*T+w.b; }
}tmp;
set<line>S; set<line>::iterator it;
int main(){
	int i;
	ios::sync_with_stdio(0);
	cin >> n;
	for (i = 1; i <= n*2; i += 2){
		cin >> p[i].realx >> p[i].realy,p[i].calc();
		cin >> p[i+1].realx >> p[i+1].realy,p[i+1].calc();
		if (p[i].x > p[i+1].x) swap(p[i],p[i+1]);
		ev[i].id = i,ev[i].tp = 1,ev[i].x = p[i].x;
		ev[i+1].id = i+1,ev[i+1].tp = 0,ev[i+1].x = p[i+1].x;
	}
	sort(ev+1,ev+(n<<1|1));
	tmp.s = -2,tmp.t = tmp.lst = 0,tmp.k = 0,tmp.b = -1e10; S.insert(tmp);
	tmp.s = -1,tmp.t = tmp.lst = 0,tmp.k = 0,tmp.b = 1e10; S.insert(tmp);
	for (i = 1; i <= n*2; ++i){
		T = ev[i].x;
		if (ev[i].tp){
			tmp.lst = tmp.s = ev[i].id,tmp.t = ev[i].id+1,tmp.calc();
			it = S.insert(tmp).first,--it;
			if (it->lst) print(p[it->lst],p[tmp.s]); it->lst = tmp.s;
		}
		else{
			tmp.s = ev[i].id-1,tmp.t = ev[i].id,tmp.calc(),it = S.find(tmp),--it;
			it->lst = tmp.t,S.erase(tmp);
		}
	}
	return 0;
}