Cod sursa(job #1027094)

Utilizator vld7Campeanu Vlad vld7 Data 12 noiembrie 2013 13:30:02
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <set>
 
using namespace std;
 
ifstream f("trapez.in");
ofstream g("trapez.out");
 
const int MAX_N = 1005;
 
int n, rez;
vector <pair <int, int> > Point;
multiset <pair <int, int> > Slopes;
 
void read() {
    f >> n;
    for (int i = 1; i <= n; i++) {
        int tmp1, tmp2;
        f >> tmp1 >> tmp2;
         
        Point.push_back (make_pair (tmp1, tmp2));
    }
}

int gcd (int A, int B) {
	if (B == 0)
		return A;
	return gcd (B, A % B);
}
 
void solve() {
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++) {
			int tmp1 = Point[j].second - Point[i].second;
			int tmp2 = Point[j].first - Point[i].first;
			int tmp3 = gcd (abs (tmp1), abs (tmp2));
			
			tmp1 /= tmp3;	tmp2 /= tmp3;
			Slopes.insert (make_pair (tmp1, tmp2));
        }
         
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++) {
			int tmp1, tmp2, tmp3;
			pair <int, int> X;
			
			tmp1 = Point[j].second - Point[i].second;
			tmp2 = Point[j].first - Point[i].first;
			tmp3 = gcd (abs (tmp1), abs (tmp2));
			
			tmp1 /= tmp3;	tmp2 /= tmp3;
			
			X = make_pair (tmp1, tmp2);
			
			int nr = Slopes.count (X);
			rez += nr * (nr - 1) / 2;
			Slopes.erase (X);
        }
}
 
int main() {
    read();
    solve();
     
    g << rez << '\n';
     
    f.close();
    g.close();
     
    return 0;
}