HDU2108-Shape of HDU
计算几何凸包问题;使用叉积判断是否所有点都满足同一方向
p1( x1 ,y1 ) , p2( x2 , y2 ) , p3(x3 , y3 ) ;
根据( x1 - x3 ) *(y2 - y3 ) - ( x2 - x3 ) * ( x1 - y3 来进行判断) ;
#include<map> #include<set> #include<list> #include<cmath> #include<ctime> #include<deque> #include<stack> #include<bitset> #include<cstdio> #include<vector> #include<cstdlib> #include<cstring> #include<iomanip> #include<numeric> #include<sstream> #include<utility> #include<iostream> #include<algorithm> #include<functional> using namespace std ; const int maxn = 10005 ; struct node { int x , y ; }edge[ maxn ] ; int judge( int a , int b , int c ) { return ( edge[ a ].x - edge[ c ].x ) * ( edge[ b ].y - edge[ c ].y ) - ( edge[ b ].x - edge[ c ].x ) * ( edge[ a ].y - edge[ c ]. y ) ; } int main() { int n , flag , temp ; while( scanf( "%d" , &n ) != EOF ) { if( !n ) { break ; } flag = 1 ; for( int i = 0 ; i < n ; ++i ) { scanf( "%d%d" , &edge[ i ].x , &edge[ i ].y ) ; } for( int i = 0 ; i < n ; ++i ) { temp = judge( i % n , ( i + 1 ) % n , ( i + 2 ) % n ) ; if( temp < 0 ) { flag = 0 ; break ; } } if( flag ) printf( "convex\n" ) ; else printf( "concave\n" ) ; } return 0; }
补充:软件开发 , C++ ,