首页 > 代码库 > UVa1606 Amphiphilic Carbon Molecules (扫描法+极角排序)
UVa1606 Amphiphilic Carbon Molecules (扫描法+极角排序)
链接：http://vjudge.net/problem/UVA-1606
分析：不妨先假设隔板一定经过至少两个点（否则可以移动隔板使其经过经过两个点，由于在隔板上的点可以看作是在任意一侧，所以总数并不会变小）。最简单的想法是，枚举两个点，然后输出两侧黑白点的个数，枚举量是O（n²），再加上统计的O（n），总时间复杂度是O（n³），太大。
可以先枚举一个基准点，然后将一条直线绕这个基准点旋转。其它点要按照相对基准点的极角排序，这里有一个技巧就是把所有黑点或者白点的坐标作一个中心对称，这样以后就只需统计直线一侧点的总数，排好序后，设边的左端点L和右端点R，初始时L=R=0，每次枚举一个点L，L和基准点的连线作为基准边，将R相对于点基准边转过180°，每当扫过一个点，就动态修改（维护）两侧的点数，直到转到180°，然后更新ans最大值，将下一个点作为左端点L，此时前任左端点被移出扫描区域cnt--，继续不断移动右端点直至180°，期间维护最大值ans就好了。
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 1000 + 5; 7 8 struct Point { 9 int x, y;10 double rad;11 bool operator < (const Point& rhs) const {12 return rad < rhs.rad;13 }14 } op[maxn], p[maxn];15 16 int n, color[maxn];17 18 bool Left(Point A, Point B) {19 return A.x * B.y - A.y * B.x >= 0;20 }21 22 int solve() {23 if (n <= 2) return 2;24 int ans = 0;25 for (int i = 0; i < n; i++) {26 int k = 0;27 for (int j = 0; j < n; j++)28 if (j != i) {29 p[k].x = op[j].x - op[i].x;30 p[k].y = op[j].y - op[i].y;31 if (color[j]) { p[k].x = -p[k].x; p[k].y = -p[k].y; }32 p[k].rad = atan2(p[k].y, p[k].x);33 k++;34 }35 sort(p, p + k);36 37 int L = 0, R = 0, cnt = 2;38 while (L < k) {39 if (L == R) { R = (R + 1) % k; cnt++; }40 while (L != R && Left(p[L], p[R])) { R = (R + 1) % k; cnt++; }41 cnt--;42 L++;43 ans = max(ans, cnt);44 }45 }46 return ans;47 }48 49 int main() {50 while (scanf("%d", &n) == 1 && n) {51 for (int i = 0; i < n; i++)52 scanf("%d%d%d", &op[i].x, &op[i].y, &color[i]);53 printf("%d\n", solve());54 }55 return 0;56 }
UVa1606 Amphiphilic Carbon Molecules (扫描法+极角排序)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。