Cod sursa(job #734608)

Utilizator elfusFlorin Chirica elfus Data 14 aprilie 2012 16:58:05
Problema Trapez Scor 100
Compilator cpp Status done
Runda simulare_elf2 Marime 1.23 kb
#include <stdio.h>
#include <algorithm>
#define NMAX 1000100
#define INF 2000000100

using namespace std;

struct panta
{
    int x, y;
} x[NMAX], point[1 << 10];

inline bool comp (panta A, panta B)
{
    return (long long)A.x * B.y < (long long)A.y * B.x;
}

int main ()
{
    int i, j, N, n = 0;

    freopen ("trapez.in", "r", stdin);
    freopen ("trapez.out", "w", stdout);

    scanf ("%d", &N);
    for (i = 1; i <= N; i ++)
        scanf ("%d%d", &point[i].x, &point[i].y);

    for (i = 1; i < N; i ++)
        for (j = i + 1; j <= N; j ++)
        {
            x[++ n].x = point[j].y - point[i].y, x[n].y = point[j].x - point[i].x;
            if (x[n].y == 0) //dreapta verticala
                x[n].x = INF, x[n].y = 1;
            if (x[n].y < 0)
                x[n].x = x[n].x * (-1), x[n].y = x[n].y * (-1);
        }

    sort (x + 1, x + n + 1, comp);

    int ans = 0, now = 1;

    for (i = 2; i <= n; i ++)
        if ((long long)x[i].x * x[i - 1].y == (long long)x[i].y * x[i - 1].x)
            now ++;
        else
        {
            ans = ans + now * (now - 1) / 2;
            now = 1;
        }

    ans = ans + now * (now - 1) / 2;
    printf ("%d", ans);
    return 0;
}