Cod sursa(job #2290117)

Utilizator LucianTLucian Trepteanu LucianT Data 25 noiembrie 2018 19:42:04
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <algorithm>
#include <vector>

#define Point pair<int,int>
using namespace std;

const int maxN=1e3+1;

struct segment{
    int x1,y1;
    int x2,y2;
};

vector<segment> lines;

int n;
long long sol;
Point v[maxN];

bool slopeCmp(const segment &a,const segment &b){
    long long dx1=a.x2-a.x1;
    long long dx2=b.x2-b.x1;
    long long dy1=a.y2-a.y1;
    long long dy2=b.y2-b.y1;

    //return dy1/dx1<dy2/dx2;
    /** evitam impartirile nedefinite
        si erorile de precizie **/
    return dy1*dx2<dy2*dx1;
}

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

    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i].first>>v[i].second;

    sort(v+1,v+n+1);

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            lines.push_back({v[i].first,v[i].second,
                               v[j].first,v[j].second});

    sort(lines.begin(),lines.end(),slopeCmp);

    for(int i=0;i<(int)lines.size();i++){
        int cnt=1;

        long long dx1=lines[i].x2-lines[i].x1;
        long long dy1=lines[i].y2-lines[i].y1;

        long long dx2=lines[i+1].x2-lines[i+1].x1;
        long long dy2=lines[i+1].y2-lines[i+1].y1;

        while(i+1<(int)lines.size() && dy1*dx2==dy2*dx1){
            cnt++;
            i++;
            dx1=dx2; dy1=dy2;

            dx2=lines[i+1].x2-lines[i+1].x1;
            dy2=lines[i+1].y2-lines[i+1].y1;
        }

        sol+=1LL*cnt*(cnt-1)/2;
    }

    cout<<sol;

    return 0;
}