http://www.lydsy.com/JudgeOnline/problem.php?id=3051
http://uoj.ac/problem/57
这道题需要平面图转对偶图，点定位，最小生成树上的倍增(NOIP2013货车运输)3个步骤。
最后一个很简单了，前两个比较麻烦。。
点定位可以用玄学的梯形剖分(并不会orz)，但这里可以离线用扫描线，类似圆的异或并那道题。
平面图转对偶图要把一条边拆成两条有向边，把每条有向边<u,v>找出和它夹角最小的<v,x>，这个过程要。。。。。。。。
算了不说了，网上的题解比我说得绝对要好得多，他们的题解也十分清晰：vfk的题解，ydc的题解，zky学长的题解。
这道题细节巨多，我在set的重载运算符上坑了好久，还有set的判重机制。
据yveh说：在set里判断\(A=B\)为真要满足\(A<B\)为假且\(B<A\)为假。
一开始没注意这个，只是比较和横坐标全局变量的交点的高低，结果扫描线扫到一个点时先加进去了一些从这个点出发的向量，后来扫到进入这个点的向量时把从这个点出发的向量删除了QAQ。最后把删除和插入分开写了，惨啊。。。
代码有272行，好长啊。。
好久没写这么长的代码了。。
或者说从来没写过这么长的代码。。。。。
#include<set>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100003;
typedef long long ll;
int in() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - 48;
return k * fh;
}
int n, M, Areanum;
struct Point {
int x, y;
Point(int _x = 0, int _y = 0)
: x(_x), y(_y) {}
Point operator + (const Point &A) const {
return Point(x + A.x, y + A.y);
}
Point operator - (const Point &A) const {
return Point(x - A.x, y - A.y);
}
} P[N * 3];
int tot = 0;
namespace INIT {
struct node {int nxt, to, h, from;} E[N << 1];
int cnt = 1, nt[N << 1], mark[N << 1], st[N << 1], point[N];
struct data {
int id; double num;
data(int _id = 0, double _num = 0) : id(_id), num(_num) {}
bool operator < (const data &A) const {
return num < A.num;
}
} D[N];
void ins(int u, int v, int w) {E[++cnt] = (node) {point[u], v, w, u}; point[u] = cnt;}
ll Cross(int a, int b) {
return (ll) P[a].x * P[b].y - (ll) P[a].y * P[b].x;
}
void init() {
int m, top, tmp, from;
ll Cro;
for (int i = 1; i <= n; ++i) {
m = 0;
for (int j = point[i]; j; j = E[j].nxt)
D[++m] = data(j, atan2(double(P[E[j].to].y - P[i].y), double(P[E[j].to].x - P[i].x)));
stable_sort(D + 1, D + m + 1);
for (int j = 1; j < m; ++j)
nt[D[j].id] = D[j + 1].id;
nt[D[m].id] = D[1].id;
// printf("---PointID = %d---m = %d---\n", i, m);
// for(int j = 1; j <= m; ++j) printf("%d ", E[D[j].id].to);
// puts("");
}
m = 0;
for (int i = 2; i <= cnt; ++i)
if (!mark[i]) {
from = E[i].from;
top = 1;
st[1] = i;
Cro = Cross(from, E[i].to);
tmp = nt[i ^ 1];
while (E[tmp].to != from) {
st[++top] = tmp;
Cro += Cross(E[tmp].from, E[tmp].to);
tmp = nt[tmp ^ 1];
}
Cro += Cross(E[tmp].from, from);
if (Cro > 0) {
mark[tmp] = -1;
while (top) mark[st[top--]] = -1;
} else {
mark[tmp] = ++m;
while (top) mark[st[top--]] = m;
}
}
// for (int i = 2; i <= cnt; ++i)
// printf("%d ---> %d RightSide : %d\n", E[i].from, E[i].to, mark[i]);
Areanum = m;
}
}
namespace MST {
struct Ed {
int u, v, w;
bool operator < (const Ed &A) const {
return w < A.w;
}
} EDGE[N << 1];
struct node {int nxt, to, w;} E[N << 1];
int tot2 = 0, cnt = 0, deep[N], f[N][18], c[N][18], point[N], fa[N];
void add(int u, int v, int w) {
EDGE[++tot2] = (Ed) {u, v, w};
// printf("%d <===dis = %d===> %d\n", u, w, v);
}
void ins(int u, int v, int w) {E[++cnt] = (node) {point[u], v, w}; point[u] = cnt;}
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void dfs(int x) {
for (int i = point[x]; i; i = E[i].nxt)
if (E[i].to != f[x][0]) {
f[E[i].to][0] = x;// printf("%d --fadis = %d--> %d\n", E[i].to, E[i].w, x);
c[E[i].to][0] = E[i].w;
deep[E[i].to] = deep[x] + 1;
dfs(E[i].to);
}
}
void init() {
stable_sort(EDGE + 1, EDGE + tot2 + 1);
for (int i = 1; i <= Areanum; ++i)
fa[i] = i;
int x, y, fx, fy, con = 0;
for (int i = 1; i <= tot2; ++i) {
x = EDGE[i].u; y = EDGE[i].v;
fx = find(x); fy = find(y);
if (fx != fy) {
++con;
if (con == Areanum) break;
fa[fx] = fy;
ins(x, y, EDGE[i].w);
ins(y, x, EDGE[i].w);
}
}
for (int i = 1; i <= Areanum; ++i)
if (!deep[i]) dfs(i);
for (int j = 1; j <= 17; ++j)
for (int i = 1; i <= Areanum; ++i) {
f[i][j] = f[f[i][j - 1]][j - 1];
c[i][j] = max(c[i][j - 1], c[f[i][j - 1]][j - 1]);
}
}
int Query(int u, int v) {
if (find(u) != find(v)) return -1;
if (deep[u] < deep[v]) swap(u, v);
int d = deep[u] - deep[v], ans = 0;
for (int i = 17; i >= 0; --i)
if ((1 << i) & d) {
ans = max(ans, c[u][i]);
u = f[u][i];
}
if (u == v) return ans;
for (int i = 17; i >= 0; --i)
if (f[u][i] != f[v][i]) {
ans = max(ans, max(c[u][i], c[v][i]));
u = f[u][i];
v = f[v][i];
}
return max(ans, max(c[u][0], c[v][0]));
}
}
int id[N * 3], nowx, rfl[N * 3];
bool cmpx(int x, int y) {
return P[x].x == P[y].x ? x < y : P[x].x < P[y].x;
}
struct setnode {
Point u, v; int kind;
setnode(Point _u = Point(0, 0), Point _v = Point(0, 0), int _kind = 0)
: u(_u), v(_v), kind(_kind) {}
};
set <setnode> S;
set <setnode> :: iterator tmp;
bool operator < (setnode A, setnode B) {
double kA = double(A.u.y) + double(nowx - A.u.x) / double(A.v.x) * A.v.y;
double kB = double(B.u.y) + double(nowx - B.u.x) / double(B.v.x) * B.v.y;
if (kA != kB) return kA < kB;
else return double(A.v.y) / double(A.v.x) < double(B.v.y) / double(B.v.x);
}
int main() {
n = in(); M = in();
int x, y, z;
for (int i = 1; i <= n; ++i) {
x = in() << 1; y = in() << 1;
P[++tot] = Point(x, y);
}
for (int i = 1; i <= M; ++i) {
x = in(); y = in(); z = in();
INIT::ins(x, y, z);
INIT::ins(y, x, z);
}
INIT::init();
z = INIT::cnt;
for (int i = 2; i <= z; i += 2)
if (INIT::mark[i] != -1 && INIT::mark[i ^ 1] != -1)
MST::add(INIT::mark[i], INIT::mark[i ^ 1], INIT::E[i].h);
MST::init();
int q = in(); double lx, ly;
for (int i = 1; i <= q; ++i) {
scanf("%lf%lf", &lx, &ly);
P[++tot] = Point(lx * 2, ly * 2);
scanf("%lf%lf", &lx, &ly);
P[++tot] = Point(lx * 2, ly * 2);
}
for (int i = 1; i <= tot; ++i)
id[i] = i;
int nowy, v;
stable_sort(id + 1, id + tot + 1, cmpx);// for (int i = 1; i <= tot; ++i) printf("%d ", id[i]); puts("");
for (int i = 1; i <= tot; ++i) {
x = id[i]; nowx = P[x].x; nowy = P[x].y;
if (x <= n) {
for (int j = INIT::point[x]; j; j = INIT::E[j].nxt) {
v = INIT::E[j].to;
if (P[v].x == P[x].x) continue;
if (P[v].x < P[x].x)
S.erase(setnode(P[v], P[x] - P[v], INIT::mark[j ^ 1]));
}
for (int j = INIT::point[x]; j; j = INIT::E[j].nxt) {
v = INIT::E[j].to;
if (P[v].x == P[x].x) continue;
if (P[v].x > P[x].x)
S.insert(setnode(P[x], P[v] - P[x], INIT::mark[j]));
}
} else {
tmp = S.upper_bound(setnode(P[x], Point(1, 0), 0));
// printf("upper_bound (%d,%d)->(%d,%d)\n", nowx, nowy, nowx + 1, nowy);
if (tmp == S.end()) {
rfl[x] = -1;
// printf("rfl[%d] = %d (%d,%d)->(%d,%d)\n", x, rfl[x], tmp->u.x, tmp->u.y, tmp->u.x + tmp->v.x, tmp->u.y + tmp->v.y);
} else {
rfl[x] = tmp->kind;
// printf("rfl[%d] = %d (%d,%d)->(%d,%d)\n", x, rfl[x], tmp->u.x, tmp->u.y, tmp->u.x + tmp->v.x, tmp->u.y + tmp->v.y);
}
}
}
for (int i = n + 1; i <= tot; i += 2) {
if (rfl[i] == -1 || rfl[i + 1] == -1)
puts("-1");
else
printf("%d\n", MST::Query(rfl[i], rfl[i + 1]));
}
return 0;
}
没有删掉丑陋而愚蠢的调试信息(调个样例都调了半天写了一大堆调试信息这样以后注定要滚粗啊！)