Cod sursa(job #1899063)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 2 martie 2017 15:10:33
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct me2{int x;int y;};
struct me{int x;int y;int ss;};
me2 v[1001];
me a[600001];
int cmpx(me2 a,me2 b)
{
    if(a.x<b.x)
        return 1;
    if(a.x==b.x&&a.y<=b.y)
        return 1;
    return 0;
}
int cmpy(me2 a,me2 b)
{
    if(a.y<b.y)
        return 1;
    if(a.y==b.y&&a.x<=b.x)
        return 1;
    return 0;
}
int cmprap(me a, me b)
{
    if(a.x*b.y<=a.y*b.x)
        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,nrl=0,nrc=0,cnt=0,j;
    long long s;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i].x,&v[i].y);
    sort(&v[1],&v[n+1],cmpy);
    for(i=2;i<=n;i++)
        if(v[i].y==v[i-1].y)
            nrc++;
    for(i=1;i<=n;i++)
    sort(&v[1],&v[n+1],cmpx);
    for(i=2;i<=n;i++)
        if(v[i].x==v[i-1].x)
            nrl++;
    s=nrl*(nrl-1)/2+nrc*(nrc-1)/2;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            if(v[i].x!=v[j].x&&v[i].y!=v[j].y)
               {
                   cnt++;
                   a[cnt].x=v[i].x-v[j].x+1;
                   a[cnt].y=v[i].y-v[j].y+1;
                   if(v[i].x>v[j].x&&v[i].y>v[j].y)
                        a[cnt].ss=1;
                   if(v[i].x<v[j].x&&v[i].y<v[j].y)
                        a[cnt].ss=2;
                   if(v[i].x>v[j].x&&v[i].y<v[j].y)
                        a[cnt].ss=3;
                   if(v[i].x<v[j].x&&v[i].y>v[j].y)
                        a[cnt].ss=4;
               }
    sort(&a[1],&a[cnt+1],cmprap);
    int l=1;
    for(i=2;i<=cnt;i++)
        {
            if(a[i].x*a[i-1].y==a[i].y*a[i-1].x&&a[i].ss==a[i-1].ss)
                l++;
            else
            {
                s+=l*(l-1)/2;
                l=1;
            }
        }
    printf("%lld",s);
    return 0;
}