首页 > 代码库 > 计算几何学习6
计算几何学习6
周末搞完了扫描线的部分
上次说的半平面交问题做法是没问题的
是按照中垂线划分平面 再求核的面积
因为是每加入一个直线就判断 所以n^2的好一点
扫描线板子(poj1177 周长并)
#include <cstdio> #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #define lc(x) (x << 1) #define rc(x) (x << 1 | 1) using namespace std; const int inf = 0x3fffffff; typedef long long LL; const int N = 100100; struct SegmentTree{ int cov, sum; int ll, rr, cnt; }T[N << 2]; struct Lin{ int x, y1, y2, d; bool operator < (const Lin & a) const{ if(x == a.x) return d > a.d; return x < a.x; } }l[N << 1]; int ax[N << 1], ay[N << 1]; int xlen, ylen, lcnt; void Build(int x, int l, int r){ T[x].sum = T[x].ll = T[x].rr = T[x].cnt = 0; if(l == r) return; int mid = l + r >> 1; Build(lc(x), l, mid); Build(rc(x), mid + 1, r); return; } void Update(int x, int l, int r){ if(T[x].cov){ T[x].ll = T[x].rr = 1; T[x].cnt = 1; T[x].sum = ay[r + 1] - ay[l]; return; } else if(l == r) T[x].ll = T[x].rr = T[x].sum = T[x].cnt = 0; else{ T[x].rr = T[rc(x)].rr; T[x].ll = T[lc(x)].ll; T[x].sum = T[lc(x)].sum + T[rc(x)].sum; T[x].cnt = T[lc(x)].cnt + T[rc(x)].cnt - (T[rc(x)].ll && T[lc(x)].rr); } return; } void Modify(int x, int l, int r, int L, int R, int d){ if(L <= l && r <= R){ T[x].cov += d; Update(x, l, r); return; } int mid = l + r >> 1; if(L <= mid) Modify(lc(x), l, mid, L, R, d); if(R > mid) Modify(rc(x), mid + 1, r, L, R, d); Update(x, l, r); return; } void Disc(int *a, int &n){ int nn = 1; sort(a + 1, a + n + 1); for(int i = 2; i <= n; i ++) if(a[i] != a[i - 1]) a[++ nn] = a[i]; n = nn; return; } int n; LL Abs(LL x){ if(x < 0) return -x; return x; } void Solve(){ xlen = 0; ylen = 0; lcnt = 0; scanf("%d", &n); int x1, y1, x2, y2; for(int i = 1; i <= n; i ++){ scanf("%d%d%d%d", &x1, &y1, &x2, &y2); l[++ lcnt] = (Lin) {x1, y1, y2, 1}; l[++ lcnt] = (Lin) {x2, y1, y2, -1}; ax[++ xlen] = x1; ay[++ ylen] = y1; ax[++ xlen] = x2; ay[++ ylen] = y2; } Disc(ax, xlen); Disc(ay, ylen); Build(1, 1, ylen - 1); for(int i = 1; i <= lcnt; i ++){ l[i].x = lower_bound(ax + 1, ax + xlen + 1, l[i].x) - ax; l[i].y1 = lower_bound(ay + 1, ay + ylen + 1, l[i].y1) - ay; l[i].y2 = lower_bound(ay + 1, ay + ylen + 1, l[i].y2) - ay; } sort(l + 1, l + lcnt + 1); int j = 1; LL ans = 0, lastans = 0; for(int i = 1; i <= lcnt; i ++){ Modify(1, 1, ylen - 1, l[i].y1, l[i].y2 - 1, l[i].d); ans += abs(T[1].sum - lastans) + 2 * T[1].cnt * (ax[l[i + 1].x] - ax[l[i].x]); lastans = T[1].sum; } printf("%lld\n", ans); return; } int main(){ Solve(); return 0; }
这是改进之后的写法了= =
poj 1177有个地方查了很久
就是统计答案的时候 是每加一条线段 都要统计一下 而不是我以前按照离散后的x坐标来求
因为求周长并时两次y轴长度相减得到的当前线段 对合并后周长的贡献 而如果按照x坐标求 就会在y轴部分漏掉一些
还有一个地方就是对于相同的x 先加入线段 再删除线段
举个例子就是
如果按照x来考虑 y轴贡献是 3 + 1 + 4 = 8
中间的1是 4 - 3 第二个边长减第一个 是无意义的
而如果按照线段来考虑结果是 3 + 2 + 1 + 4 = 10
2是第二个左侧加入后的贡献 1是第一个右侧的贡献
x轴部分就统计线段树中的区间个数就行了
或者再按x轴做一遍线段树也可以
面积并比这个简单 按x离散后的值处理也可以 少维护了区间个数的信息
其余一样
poj 1151 poj 1389 poj1177都是板子题
poj 3695 数据很奇怪
矩形个数n很小 查询m很多
感觉 m * nlogn可以过 但是被卡掉了
网上说的容斥感觉是 m * 2 ^ n 感觉很不靠谱= =但是可以过
我写的是一种 m * n ^ 2的做法
把坐标离散后可以得到 40 * 40个面积块
由于只有20个矩形 每个面积块被覆盖的信息可以由一个正数表示
在询问时扫所有块 和询问&一下 统计出结果
poj 3565
n个a类点 n个b类点
寻找一种ab一一对应的关系 使得所有线段不相交
我就是刚开始随便给一种连边方式 做n次调整
每次像冒泡一样检查 就好了
poj 2002
给你一些点 n <= 1000
问能组成多少个正方形
枚举一条边 set里找一下就好
昨天的I题
按照 从小到大 可以推出 f(2 * n + 1) = f(n) * 4 + 2 * n + 2
从大到小可以推出 f(2 * n) = 2 * (f(n) + f(n - 1))
之后就是大整数的问题了
跟着ytz学习了一点java
在智深指导下写了一发java的I
一会贴出来 当做大整数板子吧
感觉java 还是要学习一个的
接下来准备开一些解析几何的题
和固定算法的题了
计算几何学习6