巨人与鬼问题

巨人与鬼问题

#include #include #include #include #include #include using namespace std;const int maxn = 110;int n, ans[maxn];struct Node { int x, y, id; double angle; void creat_angle(const Node &node) { angle = atan2(y - node.y, x - node.x); } bool operator < (const Node &node) const { return angle < node.angle; } int type() const {return id < n ? 1 : -1;}}node[maxn*2];void solve(int left, int right) { if (left >= right) return; int i; for (i = left + 1; i <= right; i++) { if (node[i].y < node[left].y || (node[i].y == node[left].y && node[i].x < node[left].x) ) { Node temp; temp = node[i]; node[i] = node[left]; node[left] = temp; } } for (i = left + 1; i <= right; i++) { node[i].creat_angle(node[left]); } sort(node + left + 1, node + right + 1); int cnt = node[left].type(); for (i = left + 1; i <= right; i++) { cnt += node[i].type(); if (!cnt) { ans[node[left].id] = node[i].id; ans[node[i].id] = node[left].id; solve(left + 1, i - 1); solve(i + 1, right); return; } }}int main(){ scanf("%d", &n); int i, len = n << 1; for (i = 0; i < len; i++) { scanf("%d %d", &node[i].x, &node[i].y); node[i].id = i; } solve(0, len - 1); for (int i = 0; i < n; i++) { printf("%d\n", ans[i] - n + 1); } return 0;}

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