Cod sursa(job #1699120)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 6 mai 2016 08:47:05
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("trapez.in");
ofstream fout("trapez.out");
struct punct
{
    int x,y;
};
punct pct[1001];
struct dreapta
{
    int x1,y1,x2,y2;
    double panta;
    bitset<1>c;
};
dreapta a[1000001];
double panta(dreapta a)
{
    double x1=a.x1,x2=a.x2,y1=a.y1,y2=a.y2;
    return (y2-y1)/(x2-x1);
}
int qx(dreapta a, dreapta b)
{
    return a.c[0]<b.c[0] || (a.c[0]==b.c[0] && a.panta<b.panta);
}
void afis(dreapta a)
{
    cout<<a.x1<<" "<<a.y1<<" "<<a.x2<<" "<<a.y2<<"\n"<<a.panta<<" "<<a.c[0]<<"\n\n";
}
int n,i,j,lg,f,sol;
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)fin>>pct[i].x>>pct[i].y;
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
        {
            a[++lg].x1=pct[i].x;
            a[lg].x2=pct[j].x;
            a[lg].y1=pct[i].y;
            a[lg].y2=pct[j].y;
            if(a[lg].x1!=a[lg].x2)a[lg].panta=panta(a[lg]);
            else a[lg].c[0]=1;
        }
    sort(a+1,a+lg+1,qx);
    f=1;
    a[0].panta=-2000000000;
    for(i=1;i<=lg && !a[i].c[0];i++)
    {
        if(a[i].panta==a[i-1].panta)
            f++;
        else
        {
            sol+=f*(f-1)/2;
            f=1;
        }
    }
    sol+=f*(f-1)/2;
    f=0;
    for(;i<=lg;i++)
        f++;
    sol+=f*(f-1)/2;
    fout<<sol<<"\n";
    return 0;
}