Cod sursa(job #32466)

Utilizator victorsbVictor Rusu victorsb Data 17 martie 2007 21:17:15
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

#define Nmax 1024
#define mp make_pair
#define x first
#define y second

int n, ct;
pair<int, int> punct[Nmax];
pair<int, int> d[Nmax * Nmax];

void citire()
{
	int i;
	
	scanf("%d\n", &n);
	for (i = 1; i <= n; ++i)
		scanf("%d %d\n", &punct[i].x, &punct[i].y);
}

int cmp(const pair<int, int> a, const pair<int, int> b)
{
	return a.x * b.y < a.y * b.x;
}

int cmp2(const pair<int, int> a, const pair<int, int> b)
{
	return a.x * b.y == a.y * b.x;
}

void solve()
{
	int i, j, st, dr, mij, v1 = 0, v2 = 0, sol = 0;

	for (i = 1; i <= n; ++i)
		for (j = i+1; j <= n; ++j)
			d[++ct] = mp(punct[i].y - punct[j].y, punct[i].x - punct[j].x);
	
	sort(d+1, d+ct+1, cmp);

	//for (i = 1; i <= ct; ++i)
	//	printf("%lf\n", double(d[i].x) / d[i].y);

	for (i = 1; i <= ct; ++i)
	{
		st = 1; dr = ct;
		while (st <= dr)
		{
			mij = (st + dr) >> 1;
			if (!cmp(d[mij], d[i]))
			{
				v1 = mij;
				dr = mij - 1;
			}
			else
				st = mij + 1;
		}

		st = 1; dr = ct;
		while (st <= dr)
		{
			mij = (st + dr) >> 1;
			if (cmp(d[mij], d[i]) || cmp2(d[mij], d[i]))
			{
				v2 = mij;
				st = mij + 1;
			}
			else
				dr = mij - 1;
		}
		
		sol += v2 - v1 + 1;
		//printf("%d %d %d\n", i, v1, v2);
	}

	sol /= 2;
	sol -= n;

	printf("%d\n", sol);
}

int main()
{
	freopen("trapez.in", "r", stdin);
	freopen("trapez.out", "w", stdout);
	citire();
	solve();
	return 0;
}