Cod sursa(job #2067897)

Utilizator MaligMamaliga cu smantana Malig Data 16 noiembrie 2017 22:28:53
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

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

#define ll long long
#define ull unsigned long long
#define pb push_back
const int NMax = 1e3 + 50;
const int sMax = 1e6 + 5;

int N,M,Q,nrComp;
pair<int,int> p[NMax];

int euclid(int,int);

int main() {
    in>>N;

    map<pair<int,int>,int> mp;
    for (int i=1;i <= N;++i) {
        in>>p[i].first>>p[i].second;

        for (int j=1;j < i;++j) {
            int dy = p[i].second - p[j].second;
            int dx = p[i].first - p[j].first;

            if (dx == 0) {
                ++mp[pair<int,int>(0,0)];
                continue;
            }

            int gcd = euclid(abs(dx),abs(dy));
            dy /= gcd;
            dx /= gcd;

            if (dx < 0 && dy < 0) {
                dx *= -1;
                dy *= -1;
            }
            else if (dx < 0 && dy > 0) {
                dy *= -1;
                dx *= -1;
            }

            pair<int,int> panta(dx,dy);

            ++mp[panta];
        }
    }

    int ans = 0;
    map<pair<int,int>,int>::iterator it;
    for (it = mp.begin();it != mp.end();++it) {
        int val = it->second;

        ans += val*(val-1)/2;
    }

    out<<ans<<'\n';

    return 0;
}

int euclid(int a,int b) {
    return !b ? a : euclid(b,a%b);
}