Cod sursa(job #132686)

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

using namespace std;

#define NMAX 1024
#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ALL(c) c.begin(), c.end()

int N, Nr;
int X[NMAX], Y[NMAX];
int pantax[NMAX*NMAX], pantay[NMAX*NMAX];
int ind[NMAX*NMAX];

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);
            
            pantax[++Nr] = x/d;
            pantay[Nr] = y/d;
            ind[Nr] = Nr;
        }
}

int Get_Sol ()
{
    int i, ii, sz, x = 2, y = 4, cnt = 0, sol = 0;

    for (ii = 1; ii <= Nr; ++ ii)
    {
        i = ind[ii];
        //printf ("%d %d\n", pantax[i], pantay[i]);
        if (x != pantax[i] || y != pantay[i])
        {
            sol += cnt * (cnt-1) / 2;
            cnt = 1;
            x = pantax[i],  y = pantay[i];
        }    
        else
            ++ cnt;
    }
    return sol;
}

int cmp (const int a, const int b)
{
    if (pantax[a] <= pantax[b])
    {
        if (pantax[a] == pantax[b])
            return pantay[a] < pantay[b];
        return 1;        
    }
    return 0;
}

void solve ()
{
    Get_Panta ();
    sort (ind + 1, ind + Nr + 1, cmp);
    printf ("%d\n", Get_Sol ());
}

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