首页 > 代码库 > POJ2007 Scrambled Polygon
POJ2007 Scrambled Polygon
PS: 此题可以用凸包做,也可以用极角排序,关键是理解排序原理,题目说不会出现三点共线的情况。(Window 64bit %I64d, Linux %lld)
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> using namespace std; struct point { long long x, y; point(long long x=0, long long y=0):x(x),y(y) {} }; point S; point operator - (point A, point B) { return point(A.x-B.x, A.y-B.y); } double Cross(point A, point B) { return A.x*B.y - A.y*B.x; } bool cmp(point A, point B) { return Cross(A-S, B-S)>0; } vector<point> v; int main() { point t; scanf("%I64d%I64d", &S.x, &S.y); v.clear(); while(scanf("%I64d%I64d", &t.x, &t.y)!=EOF) { v.push_back(t); } sort(v.begin(), v.end(), cmp); printf("(0,0)\n"); int len = v.size(); for(int i = 0; i < len; i++) { printf("(%I64d,%I64d)\n", v[i].x, v[i].y); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。