Cod sursa(job #1899178)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 2 martie 2017 16:12:15
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct me{int x;int y;bool ss;};
me v[1001],a[1000001];
int cmmdc(int a,int b)
{
    int r;
    while(a%b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return b;
}
int cmpx(me a,me b)
{
    if(a.x<b.x||(a.x==b.x&&a.y<b.y)||a.x==b.x&&a.y==b.y&&a.ss<=b.ss)
        return 1;
    return 0;
}
int fx(int a)
{
    if(a<0)
        return -a;
    return a;
}
int main()
{
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);
    int n,i,j,cnt=0,dx,dy,cdc;
    long long s=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i].x,&v[i].y);
    sort(&v[1],&v[n+1],cmpx);
    for(i=1;i<=n-1;i++)
        for(j=i+1;j<=n;j++)
        {
            dx=v[j].x-v[i].x+1;
            dy=fx(v[j].y-v[i].y)+1;
            cdc=cmmdc(dx,dy);
            dx/=cdc;
            dy/=cdc;
            cnt++;
            a[cnt].x=dx;
            a[cnt].y=dy;
            if(v[j].y>v[i].y)
                a[cnt].ss=1;
        }
    sort(&a[1],&a[cnt+1],cmpx);
    int l=1;
    for(i=2;i<=cnt;i++)
        {
            if(a[i].x==a[i-1].x&&a[i].y==a[i-1].y&&a[i].ss==a[i-1].ss)
                l++;
            else
            {
                s+=l*(l-1)/2;
                l=1;
            }
        }
    printf("%lld",s);
    return 0;
}