当前位置: 代码迷 >> 综合 >> POJ 2007 Scrambled Polygon(极角排序)
  详细解决方案

POJ 2007 Scrambled Polygon(极角排序)

热度:95   发布时间:2023-12-08 11:00:08.0

题目链接:
POJ 2007 Scrambled Polygon

//向量a叉乘向量b小于0,说明向量b在向量a的右侧。
//极角排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
const int MAX_N=100;int n=0;struct Point {int x,y;
}point[MAX_N],origin;bool cmp(Point a,Point b)
{int x1=a.x-origin.x,y1=a.y-origin.y;int x2=b.x-origin.x,y2=b.y-origin.y;return x2*y1-x1*y2 < 0; //计算b和原点的向量p1与a和原点的向量p2的叉积是否小于0,小于0说明p1在p2的右侧
}int main()
{freopen("Bin.txt","r",stdin);scanf("%d%d",&origin.x,&origin.y);while(~scanf("%d%d",&point[n].x,&point[n].y)) {n++;}sort(point,point+n,cmp);printf("(%d,%d)\n",origin.x,origin.y);for(int i=0;i<n;i++){printf("(%d,%d)\n",point[i].x,point[i].y);}return 0;
}
  相关解决方案