Cod sursa(job #1414836)

Utilizator MihneaGhiraMihnea MihneaGhira Data 3 aprilie 2015 08:57:50
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 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)
     */
     sort(W + 1, W + M + 1);
     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;
               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 Y2) {
    return ((X2 * 1LL * Y1) - (X1 * 1LL * Y2));
}

int 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 = 2; i <= N; i ++){
          X1 = V[i-1].f;
          Y1 = V[i-1].s;
          X2 = V[i].f;
          Y2 = V[i].s;
          if(det(X1, Y1, X2, Y2) == 0){
               nr ++;
          }
          else{
               sum += (nr * (nr - 1)) / 2;
               nr = 1;
          }
     }
     sum += (nr * (nr - 1)) / 2;
     fout << sum;
     return;
}

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