| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
--!凸包(极角排序)#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<cstdlib>
#include<cmath>
const double eps=1e-8;
const double PI=3.1415926;
const int Max=1001;
#define zero(x) (((x)>0?(x):-(x))<eps)
using namespace std;
int sign(double x)
{
return (x>eps)-(x<-eps);
}
typedef struct Node
{
double x;
double y;
}point;
point list[Max],stack[Max];
int n;
int top;
double xmult(point p0,point p1,point p2)
{
return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double Distance(point p1,point p2)// 返回两点之间欧氏距离
{
return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );
}
double slope(point u,point v)
{
return (v.y-u.y)/(v.x-u.x);
}
bool cmp(point p1,point p2)
{
double temp;
temp=xmult(list[0],p1,p2);
if(temp>0)
return true;
if(temp==0&&(Distance(list[0],p1)<Distance(list[0],p2)))
return true;
return false;
}
void convex_hull()//凸包模板
{
int i;
sort(list+1,list+n,cmp);
top=1;
stack[0]=list[0];
stack[1]=list[1];
for(i=2;i<n;i++)
{
while(top>=1&&xmult(stack[top-1],stack[top],list[i])<=0)
top--;
top++;
stack[top]=list[i];
}
}
int main()
{
int m,i,j,t;
n=0;
while(cin>>list[n].x>>list[n].y)
{
n++;
}
convex_hull();
for(i=0;i<=top;i++)
{
cout<<"("<<stack[i].x<<","<<stack[i].y<<")"<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator