Cod sursa(job #2261044)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 15 octombrie 2018 21:14:57
Problema Trapez Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.93 kb
/*#include <cstdio>
#include <algorithm>

using namespace std;
struct dreapta{
    int x1;
    int y1;
    int x2;
    int y2;
};
dreapta a[1000001];
pair <int,int> v[1001],x;
int cadran (dreapta x){
    if (x.y1<=x.y2)
        return 1;
    return 2;
}
pair <int,int> tan (dreapta x){
    if (x.y1<=x.y2)
        return make_pair( x.y2-x.y1 , x.x2-x.x1 );
    return make_pair ( x.y1-x.y2 , x.x2-x.x1 );
}
int cmp (dreapta x , dreapta y){
    pair <long long,long long> xx,yy;
    xx=tan(x);
    yy=tan(y);
    if (cadran(x)!=cadran(y))
        return cadran(x)<cadran(y);
    return (xx.first*yy.second) < (xx.second * yy.first);
}
int same (int i,int j){
    pair <long long,long long> x,y;
    x=tan(a[i]);
    y=tan(a[j]);
    return ((x.first*y.second) == (x.second * y.first) && cadran(a[i])==cadran(a[j]));
}
int main()
{
    FILE *fin=fopen ("trapez.in","r");
    FILE *fout=fopen ("trapez.out","w");
    int n,i,j,m;
    long long sol,l;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d%d",&v[i].first,&v[i].second);
    sort (v+1,v+n+1);
    m=0;
    for (i=1;i<=n;i++){
        for (j=i+1;j<=n;j++){
            a[++m].x1=v[i].first;
            a[m].y1=v[i].second;
            a[m].x2=v[j].first;
            a[m].y2=v[j].second;
        }
    }
    // in a am toate segmentele
    // le sortez dupa cadran, si in caz de egalitate, dupa unghiul cu ox
    sort (a+1,a+m+1,cmp);
    for (i=1;i<=m;i++)
        fprintf(fout,"%d %d %d %d\n",a[i].x1,a[i].y1,a[i].x2,a[i].y2);
    //for (i=1;i<=m;i++){
      //  x=tan(a[i]);
        //printf ("%d %d %d %d %d %d\n",a[i].x1,a[i].y1,a[i].x2,a[i].y2,x.first,x.second);
    //}
    l=0;
    sol=0;
    for (i=1;i<=m;i++){
        if (i==1 || same(i,i-1)==0){
            sol=sol+ l*(l-1)/2;
            l=1;
        }
        else if (same (i,i-1))
            l++;
    }
    sol=sol+ l*(l-1)/2;
    fprintf (fout,"%lld",sol);
    return 0;
}*/
#include <fstream>
#include <algorithm>
#define DIM 1010
using namespace std;

ifstream fin ("trapez.in");
ofstream fout ("trapez.out");
int n,i,k,ap,sol,j;
struct punct {
    int x;
    int y;
};
punct v[DIM];

struct segment {
    int x;
    int y;
    int x2;
    int y2;
};
segment d[DIM*DIM];

int cmp2 (punct a, punct b){
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

pair<int,int> tangenta (segment a){

    pair <int,int> val;
    val.first = a.x2 - a.x;
    val.second = a.y2 - a.y;
    if (val.second < 0) val.second = -val.second;

    return make_pair(val.second,val.first);
}
int cadran (segment a){
    if (a.y <= a.y2)
        return 1;
    return 2;
}
int cmp (segment a, segment b){

    pair <int,int> nr1,nr2;

    nr1 = tangenta (a);
    nr2 = tangenta (b);

    if (cadran(a) != cadran (b))
        return cadran(a) < cadran (b);
    else
        return nr1.first*nr2.second < nr1.second*nr2.first;
}

int verif (int i, int j){

    pair <int,int> nr1,nr2;
    nr1 = tangenta (d[i]);
    nr2 = tangenta (d[j]);

    if (nr1.first*nr2.second == nr1.second*nr2.first && cadran(d[i]) == cadran(d[j]))
        return 1;
    return 0;
}
int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;

    sort (v+1,v+n+1,cmp2);
    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++){
            k++;
            d[k].x = v[i].x;
            d[k].y = v[i].y;
            d[k].x2 = v[j].x;
            d[k].y2 = v[j].y;
        }
    /// sortam dupa cadram si in caz de egalitate dupa unghi
    /// retinem tangenta
    sort (d+1,d+k+1,cmp);

   // for (i=1;i<=k;i++)
     //   fout<<d[i].x<<" "<<d[i].y<<" "<<d[i].x2<<" "<<d[i].y2<<"\n";

    ap = 1;
    for (i=2;i<=k+1;i++){
        if (verif(i,i-1))
            ap++;
        else{
            /// sol += comb ap, 2
            sol += ap*(ap-1)/2;
            ap = 1;
        }
    }
    fout<<sol;

    return 0;
}