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; }