Cod sursa(job #1413704)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 2 aprilie 2015 01:21:52
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <algorithm>
#define DIM 1000000
#define f first
#define s second
using namespace std;

ifstream fin ("trapez.in" );
ofstream fout("trapez.out");

int N, M, i, j, K, ok, X1, X2, Y1, Y2, sum;
pair <int, int> V[DIM], W[DIM]; int aux, nr;

void SetUp(){
     fin >> M;
     for(i = 1; i <= M; i ++)
          fin >> W[i].f >> W[i].s;
     /*
          SETEZ PUNCTELE CU ORIGINEA IN (O, O)
     */
     for(i = 1; i < M; i ++){
          for(j = i+1; j <= M; j ++){
               X1 = W[i].f;
               X2 = W[j].f;
               Y1 = W[i].s;
               Y2 = W[j].s;
               if(Y1 > Y2){
                    aux = X1;
                    X1 = X2;
                    X2 = aux;
                    aux = Y1;
                    Y1 = Y2;
                    Y2 = aux;
               }
               X2 -= X1; X1 = 0;
               Y2 -= Y1; Y1 = 0;
               N ++;
               V[N].f = X2;
               V[N].s = Y2;
          }
     }
     return;
}

long long det(int X1, int Y1, int X2, int Y3) {
    return X2 * 1LL * Y1 - X1 * 1LL * Y2;
}

long long cmp(pair<int, int> a, pair<int, int> b) {
    return det(a.f, a.s, b.f,b.s) >= 0;
}

void Sort(){
     sort(V + 1, V + N + 1, cmp);
     return;
}

void GetSol(){
     nr = 1;
     for(i = 1; i <= N + 1; i ++){
          X1 = V[i-1].f;
          Y1 = V[i-1].s;
          X2 = V[i].f;
          Y2 = V[i].s;
          if(det(V[i-1].f, V[i-1].s, V[i].f, V[i].s) == 0){
               nr ++;
          }
          else{
               sum += (nr * (nr - 1)) / 2;
               nr = 1;
          }
     }
     fout << sum;
     return;
}

int main(){
     SetUp();
     Sort();
     GetSol();
     return 0;
}