首页 > 其他 > 详细

POJ2007 Scrambled Polygon

时间:2014-04-27 18:13:34      阅读:504      评论:0      收藏:0      [点我收藏+]

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;
}

POJ2007 Scrambled Polygon,布布扣,bubuko.com

POJ2007 Scrambled Polygon

原文:http://blog.csdn.net/achiberx/article/details/24575975

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!