Cod sursa(job #1699184)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 6 mai 2016 16:05:21
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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 l1,c1,l2,c2;
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);
}
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)
            {
                l1=a[lg].x1,l2=a[lg].x2,c1=a[lg].y1,c2=a[lg].y2;
                a[lg].panta=(c2-c1)/(l2-l1);
            }
            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;
}