题解 UVA1606 【两亲性分子 Amphiphilic Carbon Molecules】

首先有一个结论，最优的隔板一定会经过两个点，否则可以使它经过两个点，而答案不会变差 ### 暴力思路 两点确定一条直线，可以暴力枚举两个点，连线之后再统计。时间复杂度$O(n ^ 3)$ ### 正解 接下来考虑优化 我们其实可以枚举其中一个点，然后将隔板看作一条绕这个点旋转的直线，然后动态维护答案。也就是扫描法。 枚举点是$O(n)$的，为了动态维护答案，需要将其他点按极角排序，是$O(n \log n)$的，所以总时间复杂度为$O(n ^ 2 \log n)$ 程序中还有一个小优化，就是将黑点以当前的基准点为对称中心，将它对称过去，这样只用统计直线一端的点数就是答案 ```cpp #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int read() { int k = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') k = k * 10 + c - 48, c = getchar(); return k * f; } struct zzz { int x, y, col; }p[1010]; //存初始点 struct hhh { double x, y, d; }a[1010]; //重新建系后的点 bool cmp(hhh x, hhh y) { return x.d < y.d; } bool flag(hhh x, hhh y) { //向量叉积判断x、y相差的角度是否小于180度 return x.x * y.y - x.y * y.x >= 0; } int check(int pos, int n) { //以a[pos]为基准点 int tot = 0, ans = 2, maxn = 0; //因为分隔线经过两点，所以ans初始值为2 for(int i = 1; i <= n; ++i) { if(i == pos) continue; //去除基准点 //以下为 以基准点为坐标原点，重新建系 a[++tot].x = p[i].x - p[pos].x; a[tot].y = p[i].y - p[pos].y; if(p[i].col) a[tot].x *= -1, a[tot].y *= -1; //上面提到的小优化 a[tot].d = atan2(a[tot].y, a[tot].x); } sort(a+1, a+tot+1, cmp); //按极角排序 int L = 1, R = 1; //两个指针动态维护，保证当前区间的合法性 //ans存a[L]~a[R]之间在直线同一侧的点的数量 while(L <= tot) { //维护答案 if(R == L) R = (R%tot) + 1, ++ans; while(R != L && flag(a[L], a[R])) R = (R%tot) + 1, ++ans; ++L; --ans; maxn = max(ans, maxn); } return maxn; } int solve() { //程序框架 int n = read(), ans = 0; if(n == 0) exit(0); if(n <= 2) return 2; for(int i = 1; i <= n; ++i) p[i].x = read(), p[i].y = read(), p[i].col = read(); for(int i = 1; i <= n; ++i) ans = max(ans, check(i, n)); return ans; } int main() { while(1) printf("%d\n", solve()); return 0; } ```