Cod sursa(job #132680)

Utilizator vlad_popaVlad Popa vlad_popa Data 6 februarie 2008 13:18:20
Problema Trapez Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

#define NMAX 1024
#define pb push_back
#define mp make_pair

int N;
int X[NMAX], Y[NMAX];
map < pair<int, int>, int > panta;

void read ()
{
    scanf ("%d\n", &N);
    
    int i;
    for (i = 1; i <= N; ++ i)
        scanf ("%d %d\n", X + i, Y + i);
}

inline int cmmdc(int a, int b)
{
	int c;

	while (b)
	{
		c = a % b;
		a = b;
		b = c;
	}

	return a;
}

void Get_Panta ()
{
    int i, j, x, y, d;
    
    for (i = 1; i <= N; ++ i)
        for (j = i + 1; j <= N; ++ j)
        {
            x = X[i] - X[j];
            y = Y[i] - Y[j];
            d = cmmdc (x, y);
            
            ++ panta[mp (x/d, y/d)];
        }
}

void solve ()
{
    int i, j, x, y, d, sol = 0;
    Get_Panta ();
            
    for (i = 1; i <= N; ++ i)
        for (j = i + 1; j <= N; ++ j)
        {
            x = X[i] - X[j];
            y = Y[i] - Y[j];
            d = cmmdc (x, y);
            
            if (panta[mp (x/d, y/d)])
            {
                int val = panta[mp (x/d, y/d)];
                panta[mp (x/d, y/d)] = 0;
                
                sol += val * (val-1) / 2;
            }
        }
        
    printf ("%d\n", sol);
}

int
 main ()
{
    freopen ("trapez.in", "rt", stdin);
    freopen ("trapez.out", "wt", stdout);
    
    read ();
    solve ();
    
    return 0;
}