UVa 1606 Amphiphilic Carbon Molecules——极角扫描

UVa 1606 Amphiphilic Carbon Molecules——极角扫描

#include #include #include #include #include using namespace std;const int maxn = 1010;struct Node { int x, y, col; double rad; bool operator < (const Node &node) { return rad < node.rad; }}node[maxn], tnode[maxn];bool cross(int x1, int y1, int x2, int y2) { return (x1 * y2 - x2 * y1) >= 0;}int main(){ int n; while (scanf("%d", &n) == 1 && n) { for (int i = 0; i < n; i++) { scanf("%d %d %d", &node[i].x, &node[i].y, &node[i].col); } if (n <= 3) { printf("%d\n", n); continue; } int ans = 0; for (int i = 0; i < n; i++) { int k = 0; for (int j = 0; j < n; j++) { if (j == i) continue; tnode[k].x = node[j].x - node[i].x; tnode[k].y = node[j].y - node[i].y; tnode[k].col = node[j].col; if (tnode[k].col) { tnode[k].x = -tnode[k].x, tnode[k].y = -tnode[k].y; } tnode[k].rad = atan2(tnode[k].y, tnode[k].x); k++; } sort(tnode, tnode + k); int L = 0, R = 0, cnt = 1; while (L < k) { if (R == L) { R = (R + 1) % k; cnt++; } while (R != L && cross(tnode[L].x, tnode[L].y, tnode[R].x, tnode[R].y)) { R = (R + 1) % k; cnt++; } ans = max(ans, cnt); L++, cnt--; } } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。