加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

POJ PKU 2007 按某点顺时针排序 20行

(2010-07-20 19:53:22)
标签:

poj

pku

2007

it

分类: 计算几何

题目描述:

给你一些点,让你以第一个点为基准,把剩余的点按顺时针排序。

解题报告:

排序,只要明确了任意给定的两个点之间的顺寻就可以进行。

给你两点p1, p2

如果两个点同基准点共线(叉积等于0),则如果p1的x在p2的x和基准点的x之间,则p1应该比p2靠前,否则靠后。

否则:如果p1在p2的顺时针方向(p1相对于p2的叉积大于零),则p1应该比p2考前,否则靠后。

代码很短,如下:

#include<iostream>
#include<algorithm>
using namespace std;
struct pint{int x, y;} x[1000];
bool cmp(pint p1, pint p2)
{
    int temp = (p1.x - x[0].x) * (p2.y - x[0].y) - (p2.x - x[0].x) * (p1.y - x[0].y);
    if (temp == 0) return (p1.x >= min(x[0].x, p2.x) && p1.x <= max(x[0].x, p2.x));
    else return temp > 0;
}
int n = 0;
int main()
{
    while(scanf("%d%d", &x[n].x, &x[n].y) != EOF) n++;
    sort(x + 1, x + n, cmp);
    for(int i = 0; i < n; i++) printf("(%d,%d)\n", x[i].x, x[i].y);
    return 0;
}

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有