Cod sursa(job #1026654)

Utilizator george_stelianChichirim George george_stelian Data 11 noiembrie 2013 20:49:32
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <cstdlib>

using namespace std;

struct punct1
{
    int x,y;
};
struct punct2
{
    int x,y;
    char a;
};

punct1 v1[1000];
punct2 v[600000],aux;
long long int s;
int i,j,n,mid,x,y,a,b,nr;

void sort(int st,int dr)
{
    int i=st,j=dr;
    x=v[(i+j)/2].x;
    y=v[(i+j)/2].y;
    do
    {
        while(v[i].x*y<v[i].y*x) i++;
        while(v[j].x*y>v[j].y*x) j--;
        if(i<=j)
        {
            aux=v[i];v[i]=v[j];v[j]=aux;
            i++;j--;
        }
    }while(i<=j);
    if(i<dr) sort(i,dr);
    if(j>st) sort(st,j);
}

int main()
{
    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d%d",&v1[i].x,&v1[i].y);
    nr=-1;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            v[++nr].x=abs(v1[i].y-v1[j].y);
            v[nr].y=abs(v1[i].x-v1[j].x);
            if((v1[j].x>=v1[i].x && v1[j].y>=v1[i].y)||(v1[j].x<=v1[i].x && v1[j].y<=v1[i].y)) v[nr].a=0;
            else v[nr].a=1;
        }
    }
    sort(0,nr);
    x=v[1].x;
    y=v[1].y;
    if(v[1].a==0) a=1;
    else b=1;
    for(i=1;i<=n;i++)
    {
        if(v[i].x*y==v[i].y*x)
        {
            if(v[i].a==0) a++;
            else b++;
            continue;
        }
        s+=a*(a-1)/2+b*(b-1)/2;
        x=v[i].x;
        y=v[i].y;
        a=0;b=0;
        if(v[i].a==0)a=1;
        else b=1;
    }
    s+=a*(a-1)/2+b*(b-1)/2;
    printf("%lld",s);
    fclose(stdin);fclose(stdout);
    return 0;
}