Cod sursa(job #1743798)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 18 august 2016 19:16:15
Problema Trapez Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 1050

using namespace std;

struct fractie
{
    int sus, jos;
    fractie(int _sus = 0, int _jos = 1)
    {
    	 sus = _sus;
    	 jos = _jos;
    	 if (sus < 0 && jos < 0) sus *= -1, jos *= -1;
    }
    bool operator==(fractie f)
    {
		return 1LL*this->sus*f.jos == 1LL*f.sus*this->jos;
    }
    bool pozitiv()
    {
    	return sus > 0 && jos > 0;
    }
};

fractie a[MAXN*MAXN];
int n, k;
int xes[MAXN], yes[MAXN];

bool cmp(fractie e, fractie f)
{
	if (e.pozitiv() && !f.pozitiv())
		return 0;
	else if (!e.pozitiv() && f.pozitiv())
		return 1;
	return 1LL*e.sus*f.jos < 1LL*f.sus*e.jos;
}

void citire()
{
	int x, y;
	scanf("%d", &n);
    for (int i = 1; i <= n; i++)
		scanf("%d %d", &xes[i], &yes[i]);
	for (int i = 1; i <= n; i++)
		for (int j = i+1; j <= n; j++)
			a[++k] = fractie(yes[j]-yes[i], xes[j]-xes[i]);
	sort(a+1, a+k+1, cmp);
}

void solve()
{
    int rez = 0;
    int run = 1;
    for (int i = 2; i <= k; i++) {
        if (a[i] == a[i-1])
			run++;
        else {
			rez += run*(run-1) / 2;
            run = 1;
        }
    }
    rez += run*(run-1) / 2;
    printf("%d", rez);
}

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

    citire();
    solve();

    return 0;
}