ural 1207 Median on the Plane

极角排序

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 30000
using namespace std; struct point
{
double x,y;
int num;
}p[maxn];
point pp;
double cross(const point &a,const point &b,const point &c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(const point &a,const point &b)
{
if(cross(p[],a,b)>) return ;
else return ;
}
int main()
{
int n;
int k=;
scanf("%d",&n);
for(int i=; i<n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
p[i].num=i+;
if(p[i].y<p[k].y||(p[k].y==p[i].y&&p[i].x<p[k].x)) k=i;
}
swap(p[],p[k]);
sort(p+,p+n,cmp);
printf("%d %d\n",p[].num,p[n/].num);
return ;
}
上一篇:洛谷P2242 公路维修问题


下一篇:P1265 公路修建 洛谷