Cod sursa(job #614232)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 5 octombrie 2011 21:28:27
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define NMax 1005
#define x first
#define y second

using namespace std;

int N, S;
pair <int, int> P[NMax];
vector < pair <int, int> > M;

inline int Abs (int x)
{
    if (x<0)
    {
        return -x;
    }
    return x;
}

int CMMDC (int a, int b)
{
    while (b!=0)
    {
        int r=a%b;
        a=b;
        b=r;
    }
    if (a==0)
    {
        a=1;
    }
    return a;
}

inline bool Compare (pair <int, int> A, pair <int, int> B)
{
    if (A.x<B.x)
    {
        return true;
    }
    if (A.x>B.x)
    {
        return false;
    }
    if (A.y<B.y)
    {
        return true;
    }
    return false;
}

inline bool CompareM (unsigned i, unsigned j)
{
    if (M[i].x==M[j].x and M[i].y==M[j].y)
    {
        return true;
    }
    return false;
}

pair <int, int> GetM (int i, int j)
{
    int a=P[j].x-P[i].x;
    int b=P[j].y-P[i].y;
    int c=CMMDC (Abs (a), Abs (b));
    a/=c;
    b/=c;
    return make_pair (a, b);
}

void Read ()
{
    freopen ("trapez.in", "r", stdin);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d %d", &P[i].x, &P[i].y);
        for (int j=i-1; j>0; --j)
        {
            M.push_back (GetM (i, j));
        }
    }
}

void Print ()
{
    freopen ("trapez.out", "w", stdout);
    printf ("%d\n", S);
}

int main()
{
    Read ();
    sort (M.begin (), M.end (), Compare);
    int NM=0;
    for (unsigned i=1; i<M.size (); ++i)
    {
        if (CompareM (i, i-1))
        {
            ++NM;
        }
        else
        {
            S+=(NM*NM+1/2);
            NM=0;
        }
    }
    Print ();
    return 0;
}