Cod sursa(job #1146519)

Utilizator classiusCobuz Andrei classius Data 19 martie 2014 08:24:13
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
//#include <iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>

using namespace std;

ifstream cin("trapez.in");
ofstream cout("trapez.out");

int i,j,a,b,s,n;
vector<pair<int,int> > v,u;

inline int comb(int x){
    return(x)*(x-1)/2;
}

bool cmp(const pair<int,int>& p1,const pair<int,int>& p2){
    if(p1.first==p2.first){
        return p1.second<p2.second;
    }
    return p1.first<p2.first;
}

int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a>>b;
        v.push_back(make_pair(a,b));
    }

    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int x=v[i].first-v[j].first;
            int y=v[i].second-v[j].second;

            if(x==0){
                u.push_back(make_pair(0,1));
            }else if(y==0){
                u.push_back(make_pair(1,0));
            }else{
                int a,b,c;
                a=abs(x);
                b=abs(y);
                while(b){
                    c=a%b;
                    a=b;
                    b=c;
                }
                x/=a;
                y/=a;
                if(x<0 && y<0){
                    x=-x;
                    y=-y;
                }else if(x>0 && y<0){
                    x=-x;
                    y=-y;
                }
                u.push_back(make_pair(x,y));
            }
        }
    }

    sort(u.begin(),u.end(),cmp);

    int s=0,nr=1,i=0;
    for(unsigned j=1;j<u.size();j++){
        if(u[i]!=u[j]){
            s+=comb(nr);
            i=j;
            nr=1;
            continue;
        }
        nr++;
    }

    s+=comb(nr);
    cout<<s;

    return 0;
}