Cod sursa(job #1451153)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 16 iunie 2015 11:42:22
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<fstream>
#include<algorithm>
#include<iostream>
using namespace std;
ifstream in("trapez.in");
ofstream out("trapez.out");
const int NMAX = 1000005;
const int INF = 1 << 30;

struct dreapta{
    int a,b;
};

dreapta v[NMAX * 2];

int A[NMAX],B[NMAX],n,nr;

void read()
{

    in>>n;
    for(int i = 1 ; i <= n ; ++i)
        in>>A[i]>>B[i];
    in.close();

}

bool not_equal(int x1,int y1,int x2,int y2)
{

    if(x1 == x2 && y1 == y2)
        return false;
    return true;
}

double eval(int x,int y)
{

    if(y == 0)
        return (double)INF;
    return (double)x/y;
}

bool cmp(dreapta a,dreapta b)
{

    return eval(a.a,a.b) < eval(b.a,b.b);
}

void solve()
{

    for(int i = 1 ; i < n ; ++i)
        for(int j = i+1 ; j <= n  ; ++j){

            int p1 = B[i] - B[j];
            int p2 = A[i] - A[j];
            v[++nr].a = p1;
            v[nr].b = p2;
        }
    sort(v + 1,v + nr + 1,cmp);
    int sol = 0,ct = 1;
    for(int i = 2 ; i <= nr  ;++i)
        if(v[i].a * v[i-1].b == v[i].b * v[i-1].a)
            ++ct;
        else{
            sol += (ct*(ct-1))/2;
            ct = 1;
        }
    sol += (ct * (ct - 1))/2;
    out<<sol;
}

int main()
{

    read();
    solve();
    return 0;
}