Cod sursa(job #2287404)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 21 noiembrie 2018 20:45:35
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("trapez.in");
ofstream cout("trapez.out");
struct dr{
    long long x1,y1,x2,y2;
} d[1000005];
struct pc{
    int x,y;
} t[1005];
int n,k,x[1005],y[1005];
long long ans;
int cp(pc i,pc j){
    return (i.x<j.x)||(i.x==j.x && i.y<j.y);
}
int cmp(dr i,dr j){
    long long d1,d2,d3,d4;
    d1=i.y1-i.y2; d2=i.x1-i.x2;
    d3=j.y1-j.y2; d4=j.x1-j.x2;
    return d1*d4<d2*d3;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>t[i].x>>t[i].y;
    sort(t+1,t+n+1,cp);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++){
            ++k;
            d[k].x1=t[i].x;
            d[k].y1=t[i].y;
            d[k].x2=t[j].x;
            d[k].y2=t[j].y;
        }
    sort(d+1,d+k+1,cmp);
    for(int i=1;i<k;i++){
        long long cnt=1;
        long long d1,d2,d3,d4;
        d1=d[i].y1-d[i].y2; d2=d[i].x1-d[i].x2;
        d3=d[i+1].y1-d[i+1].y2; d4=d[i+1].x1-d[i+1].x2;
        while(i<k && d1*d4==d2*d3){
            ++cnt; ++i;
            d1=d[i].y1-d[i].y2; d2=d[i].x1-d[i].x2;
            d3=d[i+1].y1-d[i+1].y2; d4=d[i+1].x1-d[i+1].x2;
        }
        ans=ans+cnt*(cnt-1)/2;
    }
    cout<<ans;
}