hdu 5020 排列組合＋stl map （或者離散化）

首先為了重複計算，先對點進行排序，然後標明一個點，找到這個點斜率相同的點，然後利用排列組合知識就能知道點對有c(2,n)個，是以隻需枚舉每個點，找到它序位後面的點中到它斜率相同的點為集合，然後每個集合中取c(2,n),就能得到答案，利用map可以省去離散化Ｈａｓｈ的過程

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <map>
#define MAX 1007

using namespace std;

typedef long long LL;
typedef pair<long long , long long> PLL;

map<PLL,LL> mp;

struct Point
{
    LL x,y;
    bool operator < ( const Point& a ) const
    {
        if ( x == a.x ) return y < a.y;
        return x < a.x;
    }
}p[MAX];

LL gcd ( LL a , LL b )
{
    return b == 0 ? a : gcd ( b , a%b );
}

int t,n;

int main ( )
{
    scanf ( "%d" , &t );
    while ( t-- )
    {
        scanf ( "%d" , &n );
        for ( int i = 1 ; i <= n ; i++ )
            scanf ( "%lld%lld" , &p[i].x , &p[i].y );
        sort ( p+1 , p+n+1 );
        LL ans = 0;
        for ( int i = 1 ; i < n ; i++ )
        {
            mp.clear();
            for ( int j = i+1 ; j <= n ; j++ )
            {
                LL x = p[j].x - p[i].x;
                LL y = p[j].y - p[i].y;
                LL g = gcd ( x , y );
                x /= g , y /= g;
                mp[make_pair( x , y )]++;
            }
            map<PLL,LL>::iterator it;
            for ( it= mp.begin(); it != mp.end() ; it++ )
            {
                LL temp = it->second;
                ans += temp*(temp-1)/2;
            }
        }
        printf ( "%lld\n" , ans );
    }
}