CEOI2020 道路（Roads） Solution

直接来构造。

考虑扫描线。从左到右扫，考虑当前扫到了一个左端点，我们把这个左端点连到其他点上。

我们可以找到这个点下方离他最近的线段，并且记下每条线段上方在扫描线左侧且最靠右，与这条线段中间没有其他线段的点，然后直接把左端点连到这样的点上就行了。容易证明这样的连发一定是对的。

找线段的过程用一个\(\text{set}\)来维护，对于每条线段记一个最后出现的在这条线段。

对于一些不好分类讨论的特殊情况，我们可以在所有线段的最下方加上一条直线，然后因为可能有斜率不存在的线段，我们可以把所有点随机旋转一下。就做完了

#include <cstdio>

#include <iostream>

#include <cmath>

#include <set>

#include <algorithm>

#define LL long long

#define db long double

using namespace std;

inline int read() {

	int res = 0, flag = 0; char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') flag = 1;

	for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);

	if(flag) res = ~res + 1; return res;

}

const db t = 1007.0/1009.0, cost = cos(t), sint = sin(t);

const db inf = 1e10;

const int N = 1e5 + 10;

int n;

struct Point {

	int id;

	db x, y;int rx, ry;

	inline void get() {x = rx * cost - ry * sint, y = ry * cost + rx * sint;}

	inline void print() {printf("%d %d ",rx,ry);}

	inline void print1() {printf("%Lf %Lf ",x,y);}

	inline bool operator < (const Point y) const{return (x < y.x);}

}p[N << 1], q[N << 1];

db nx;

struct Segment {

	int l, r; mutable int lst; db k, b;

	inline void get() {k = (p[l].y - p[r].y) / (p[l].x - p[r].x), b = p[l].y - p[l].x * k;}

	inline void print() {printf("seg %Lf %Lf\n",k,b);}

	inline bool operator < (const Segment y) const{return nx * k + b < nx * y.k + y.b;}

};

set <Segment> S; set <Segment>::iterator it;

int main() {

	n = read();

	for(register int i = 1; i <= n + n; i += 2) {

		p[i].rx = read(), p[i].ry = read(), p[i].get();

		p[i + 1].rx = read(), p[i + 1].ry = read(), p[i + 1].get();

		if(p[i + 1] < p[i]) swap(p[i], p[i + 1]); p[i].id = i, p[i + 1].id = i + 1;

		q[i] = p[i], q[i + 1] = p[i + 1];

	}

	sort(q + 1, q + n + n + 1);

	Segment tmp;

	tmp.k = 0, tmp.b = -inf, tmp.lst = 0, S.insert(tmp);

	for(register int i = 1, id; i <= n + n; ++i) {

		nx = q[i].x, id = q[i].id;

		if(id & 1) { // left

			tmp.l = id, tmp.r = id + 1, tmp.lst = id, tmp.get();

			it = S.insert(tmp).first; --it;

			if(it->lst) p[it->lst].print(), p[id].print(), printf("\n");

			it->lst = id;

		}

		else { // right

			tmp.l = id - 1, tmp.r = id, tmp.lst = id, tmp.get();

			it = S.find(tmp); --it;

			it->lst = id, S.erase(tmp);

		}

	}

}

CEOI2020 道路（Roads） Solution的相关教程结束。