Cod sursa(job #1691972)

Utilizator horatiudumhoratiu horatiudum Data 19 aprilie 2016 22:01:27
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <cmath>
#include <iomanip>
#include <fstream>
#include <algorithm>
#define MAX 1003
#define MAXQ 0.123123123
#define MAXQ2 0.321321321

using namespace std;

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

double v[MAX*MAX];
pair<double, double> pct[MAX];

int main() {

    int n;
    in >> n;

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

    int T = 1;

    for(int i = 1; i <= n; i++) {

        for(int j = i+1; j <= n; j++) {

            if(pct[i].first == pct[j].first) {

                v[T++] = MAXQ2;
                continue;

            }

            if(pct[i].second == pct[j].second) {

                v[T++] = MAXQ;
                continue;

            }

            v[T++] = (double)(pct[i].first-pct[j].first)/(pct[i].second-pct[j].second);

        }

    }

    sort(v+1, v+T+1);
    //cout << setprecision(20);
    int upb;
    int upd;
    long long rez = 0;

    for(int i = 1; i <= T; i++) {
        upb = upper_bound(v+1, v+T+1, v[i])-v-1;
        upd = upb-i;
        rez += upd*(upd+1)/2;
        //cout << i << " " << upb << '\n';
        i = upb;
        //cout << v[i] << " ";
    }

    out << rez << '\n';

    return 0;
}