POJ 2007計算幾何水題
1614 ワード
凸多角形の頂点を反時計回りに並べ替え、始点が原点で第2象限のない点です.
水の...
水の...
/***********************
*Creator:Sevenster *
*Time:2012.08.01 13:47*
*PID:POJ 2007 *
***********************/
#include<iostream>
#include<cmath>
#include<algorithm>
#define EPS 1e-6
using namespace std;
class CPoint
{
public:
double x, y;
CPoint( double a= 0, double b= 0 )
{
this->x= a;
this->y= b;
}
}point[55];
class CVector
{
public:
double x, y;
CVector( double a= 0, double b= 0 )
{
this->x= a;
this->y= b;
}
};
CVector operator-( CPoint b, CPoint a )
{
return CVector( b.x- a.x, b.y- a.y );
}
double operator^( CVector p,CVector q )
{
return p.x* q.y- p.y* q.x;
}
int sign( double x )
{
if( fabs(x)<EPS )
return 0;
return x>0?1:-1;
}
double length( CVector p )
{
return sqrt( fabs( p.x* p.x+ p.y* p.y ) );
}
bool cmp( CPoint p,CPoint q )
{
int flag=sign( ( p- point[0])^( q- point[0]) );
if( flag==0 )
return length( p- point[0] )<length( q- point[0] );
return flag==1;
}
int main()
{
//freopen( "test.in","r",stdin );
//freopen( "test.out","w",stdout );
int pcnt=0;
while( scanf( "%lf %lf", &point[pcnt].x, &point[pcnt].y )!=EOF )
pcnt++;
sort( point+ 1, point+ pcnt, cmp );
for( int i= 0; i< pcnt; i++ )
printf( "(%.0lf,%.0lf)
", point[i].x, point[i].y );
return 0;
}