Cod sursa(job #768128)

Utilizator silviu982001Borsan Silviu silviu982001 Data 16 iulie 2012 01:42:40
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<fstream>
#include<algorithm>
#define maxn 1005

using namespace std;

ifstream f("trapez.in");
ofstream g("trapez.out");

struct panta
{
    long long x;
    long long y;
} a[maxn],b[maxn*maxn],c[maxn*maxn],k;

int n,i,j,p,q,r;

long long rez;

long long mod(int a)
{
    if(a<0) return -a;
    return a;
}

bool fcomp(panta a, panta b)
{
    return a.x*b.y<a.y*b.x;
}

bool comp(panta a,panta b)
{
    return a.x*b.y==a.y*b.x;
}

int main()
{
    f>>n;

    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;

    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j)
        {
            k.x=a[i].y-a[j].y;
            k.y=a[i].x-a[j].x;
            if((k.x<0&&k.y<0)||k.x==0||k.y==0)
                k.x=mod(k.x),k.y=mod(k.y),b[++p]=k;
            else
                if(k.x<0||k.y<0)
                    k.x=mod(k.x),k.y=mod(k.y),c[++q]=k;
                else
                    b[++p]=k;
        }

    sort(b+1,b+p+1,fcomp);
    sort(c+1,c+q+1,fcomp);

    r=1;
    for(i=2;i<=p;++i)
        if(!comp(b[i],b[i-1]))
            rez+=(i-r)*(i-r-1)/2,r=i;

    rez+=(i-r)*(i-r-1)/2;

    r=1;

    for(i=2;i<=q;++i)
        if(!comp(c[i],c[i-1]))
            rez+=(i-r)*(i-r-1)/2,r=i;

    rez+=(i-r)*(i-r-1)/2;

    g<<rez<<"\n";

    f.close();
    g.close();

    return 0;
}