zoj 2983 Rectangular Polygons

zoj 2983 Rectangular Polygons,第1张

zoj 2983 Rectangular Polygons
#include <cstdlib>#include <cctype>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>#include <vector>#include <string>#include <iostream>#include <sstream>#include <map>#include <set>#include <queue>#include <stack>#include <fstream>#include <utility>#include <ctime>#include <climits>using namespace std;typedef long long LL;typedef pair<int, int> PII;#define MP make_pairconst int MAXN = 1024;struct Point { int x, y, id; bool operator<(const Point& rhs) const { return id < rhs.id; }}p[MAXN];int nxt[MAXN][2];bool vist[MAXN];bool cmp1(Point a, Point b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y;}bool cmp2(Point a, Point b) { if (a.y != b.y) return a.y < b.y; return a.x < b.x;}LL cross(Point a, Point b) { return b.x * a.y - b.y * a.x;}const char *str = "NESW";int main() { int N; while (scanf("%d", &N), N) { for (int i = 0; i < N; ++i) { scanf("%d %d", &p[i].x, &p[i].y); p[i].id = i; } sort(p, p + N, cmp1); for (int i = 0; i < N; i += 2) { nxt[p[i].id][0] = p[i+1].id; nxt[p[i+1].id][0] = p[i].id; } sort(p, p + N, cmp2); for (int i = 0; i < N; i += 2) { nxt[p[i].id][1] = p[i+1].id; nxt[p[i+1].id][1] = p[i].id; } sort(p, p + N); int u = 0, v = nxt[0][0]; vector<int> vec; LL area = 0; memset(vist, false, sizeof(vist)); for (int i = 0; i < N; ++i) { vist[u] = vist[v] = true; area += cross(p[u], p[v]); if (p[u].x == p[v].x) { vec.push_back((p[u].y > p[v].y) * 2); } else { vec.push_back((p[u].x > p[v].x) * 2 + 1); } u = v; v = vist[nxt[v][0]] ? nxt[v][1] : nxt[v][0]; vist[nxt[u][0]] = false; } if (area < 0) reverse(vec.begin(), vec.end()); area = area < 0 ? 2 : 0; for (int i = 0; i < vec.size(); ++i) { putchar(str[(vec[i]+area)%4]); } puts(""); } return 0;}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/4925820.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-11-12
下一篇 2022-11-12

发表评论

登录后才能评论

评论列表(0条)

保存