本文主要是介绍【HDU】5020 Revenge of Collinearity 极角排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】5020 Revenge of Collinearity
题目分析：水计算几何，极角排序，第一关键字y轴，第二关键字x轴。
话说不用long long 竟然比用了慢，果然我不懂计算机的心。
代码如下：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;typedef long long LL ;#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )const int MAXN = 1005 ;
const int MAXE = 4005 ;
const int INF = 0x3f3f3f3f ;
const double eps = 1e-8 ;struct Point {int x , y ;double r ;Point () {}Point ( int x , int y ) : x ( x ) , y ( y ) {}Point operator - ( const Point& p ) const {return Point ( x - p.x , y - p.y ) ;}
} p[MAXN] , a[MAXN] ;int n ;int cmp1 ( const Point& a , const Point& b ) {if ( a.y != b.y ) return a.y < b.y ;return a.x < b.x ;
}int cmp2 ( const Point& a , const Point& b ) {return a.r < b.r ;
}bool cross ( const Point& a , const Point& b ) {return ( LL ) a.x * b.y - ( LL ) a.y * b.x == 0 ;
}void solve () {int ans = 0 ;scanf ( "%d" , &n ) ;rep ( i , 0 , n ) scanf ( "%d%d" , &p[i].x , &p[i].y ) ;sort ( p , p + n , cmp1 ) ;rep ( i , 0 , n - 2 ) {int top = 0 ;rep ( j , i + 1 , n ) {a[top] = p[j] - p[i] ;a[top].r = atan2 ( ( double ) a[top].y , ( double ) a[top].x ) ;//if ( a[top].r < 0 ) printf ( "2333\n" ) ;top ++ ;}sort ( a , a + top , cmp2 ) ;rep ( j , 1 , top ) {int tmp = 1 ;while ( j < top && cross ( a[j] , a[j - 1] ) ) {++ tmp ;++ j ;}ans += tmp * ( tmp - 1 ) / 2 ;}}printf ( "%d\n" , ans ) ;
}int main () {int T ;scanf ( "%d" , &T ) ;while ( T -- ) solve () ;return 0 ;
}这篇关于【HDU】5020 Revenge of Collinearity 极角排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
