栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 2983 Rectangular Polygons

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/378094.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号