Cod sursa(job #2238866)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 8 septembrie 2018 00:39:18
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;
ifstream in("trapez.in");
ofstream out("trapez.out");

const int NMAX = 1005;

map<int, int> m[NMAX];

struct Data {
    ll x, y;
}v[NMAX];

vector<pair<ll, ll> > sorted;

ll euclid(ll a, ll b) {
    ll r;
    while(b) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int n;
    in >> n;
    for(int i = 1; i <= n; i ++)
        in >> v[i].x >> v[i].y;
    vector<int> special;
    for(int i = 1; i <= n; i ++) {
        for(int j = i + 1; j <= n; j ++) {
            if(v[i].x != v[j].x) {
                ll a = v[i].y - v[j].y;
                ll b = v[i].x - v[j].x;
                ll d = euclid(abs(a), abs(b));
                a /= d;
                b /= d;
                if(a < 0 && b > 0) {
                    a *= -1;
                    b *= -1;
                } else if(a < 0 && b < 0) {
                    a *= -1;
                    b *= -1;
                }
                if(a == 0)
                    b = 0;
                //cout << i << " " << j << " -> " << a << ", " << b << endl;
                sorted.push_back({a, b});
            } else {
                special.push_back(v[i].x);
            }
        }
    }

    sort(sorted.begin(), sorted.end());
    int i = 0;
    ll ans = 0;
    while(i < sorted.size()) {
        ll nr = 1;
        while(i < sorted.size() + 1 && sorted[i] == sorted[i + 1]) {
            nr ++;
            i ++;
        }
        ans += (nr * (nr - 1) / 2);
        //cout << sorted[i].first << " " << sorted[i].second << endl;
        i ++;
    }

    sort(special.begin(), special.end());
    int j = 0;
    while(j < special.size()) {
        int last = j;
        ans += j;
        if(j < special.size() + 1 && special[j] == special[j + 1]) {
            j ++;
            ans += last;
        }
        j ++;
    }

    out << ans;
    return 0;
}