Cod sursa(job #1758688)

Utilizator silkMarin Dragos silk Data 17 septembrie 2016 17:45:01
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <algorithm>
#define NMax 1000000
#define TMax 1000
#define ABS(x)((x)>0?(x):(-(x)))
using namespace std;

struct oij{ int x,y; };
oij pct[TMax+1],seg[NMax+1];

bool cmp(const oij A, const oij B)
{
    if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
}

void gcd(int& x, int& y)
{
    if( !x ) { y = 1; return; }
    else if( !y ) { x = -1; return; }

    int r,a=ABS(x),b=ABS(y);

    while(b){ r=a%b; a=b; b=r; }
    x/=a; y/=a;
}

int main(){
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);

    int i,j,N,t,ans=0;

    scanf("%d",&N);
    for(i = 1; i <= N; ++i) scanf("%d %d",&pct[i].x,&pct[i].y);
    for(t = 0, i = 1; i < N; ++i)
        for(j = i+1; j <= N; ++j)
        {
            seg[++t].x = pct[j].x-pct[i].x;
            seg[t].y = pct[j].y-pct[i].y;
            gcd( seg[t].x, seg[t].y );
            if( seg[t].x < 0 && seg[t].y < 0 ) { seg[t].x *= -1; seg[t].y *= -1; }
            else if( seg[t].y < 0 ) { seg[t].x *= -1; seg[t].y *= -1; }
        }

    sort(seg+1,seg+t+1,cmp);

    for(i = 1; i <= t; )
    {
        for(j = i; j <= t && seg[i].x==seg[j].x && seg[i].y==seg[j].y; ++j);
        ans += (j-i)*(j-i-1)/2;
        i = j;
    }

    printf("%d\n",ans);



return 0;
}