【【BZOJ|【BZOJ 3051】【UOJ #57】【WC 2013】平面图】http://www.lydsy.com/JudgeOnline/problem.php?id=3051
http://uoj.ac/problem/57
这道题需要平面图转对偶图，点定位，最小生成树上的倍增(NOIP2013货车运输)3个步骤。
最后一个很简单了，前两个比较麻烦。。
点定位可以用玄学的梯形剖分(并不会orz)，但这里可以离线用扫描线，类似圆的异或并那道题。
平面图转对偶图要把一条边拆成两条有向边，把每条有向边找出和它夹角最小的，这个过程要。。。。。。。。
算了不说了，网上的题解比我说得绝对要好得多，他们的题解也十分清晰：vfk的题解，ydc的题解，zky学长的题解。
这道题细节巨多，我在set的重载运算符上坑了好久，还有set的判重机制。
据yveh说：在set里判断\(A=B\)为真要满足\(A 一开始没注意这个，只是比较和横坐标全局变量的交点的高低，结果扫描线扫到一个点时先加进去了一些从这个点出发的向量，后来扫到进入这个点的向量时把从这个点出发的向量删除了QAQ。最后把删除和插入分开写了，惨啊。。。
代码有272行，好长啊。。
好久没写这么长的代码了。。
或者说从来没写过这么长的代码。。。。。
#include
#include
#include
#include
#include
#include
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) {}
};
setS;
set:: 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;
}
没有删掉丑陋而愚蠢的调试信息(调个样例都调了半天写了一大堆调试信息这样以后注定要滚粗啊！)
转载于:https://www.cnblogs.com/abclzr/p/5971289.html
推荐阅读
