Cod sursa(job #908553)

Utilizator gener.omerGener Omer gener.omer Data 9 martie 2013 17:12:53
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <algorithm>

#define NMAX 1005
#define MAX 0xAAAAAAAA

using namespace std;

int x[NMAX], y[NMAX], N, res = 0;

struct panta
{
	int i, j;
	int x, y;
};

panta vp[NMAX * NMAX];

bool cmp(panta p1, panta p2)
{
	int s1 = 0, s2 = 0;
	if(p1.x < 0) ++s1;
	if(p1.y < 0) ++s1;
	if(p2.x < 0) ++s2;
	if(p2.y < 0) ++s2;
	s1 %= 2, s2 %= 2;
	if(s1 != 0 && s2 == 0)
		return true;
	else if(s1 == 0 && s2 != 0)
		return false;
	else{
		int val = (abs(p1.y) * abs(p2.x) - abs(p1.x) * abs(p2.y));
		if(s1 == 0 && s2 == 0)
			return (val < 0);
		return (val > 0);
	}
}

int main()
{
	ifstream in("trapez.in");
	ofstream out("trapez.out");
	
	in >> N;
	for(int i = 0; i < N; ++i)
		in >> x[i] >> y[i];

	int t = 0;
	for(int i = 0; i < N - 1; ++i)
		for(int j = i + 1; j < N; ++j)
		{
			vp[t].i = i;
			vp[t].j = j;
			vp[t].x = x[i] - x[j];
			vp[t].y = y[i] - y[j];			
			t++;
		}
	
	sort(vp, vp + t, cmp);
	
	//for(int i = 0; i < t; ++i)
	//	cout << vp[i].x << " " << vp[i].y << endl;
	
	for(int i = 0; i < t;)
	{
		int j = i + 1;
		for(; j < t;)
		{
			if((vp[i].x * vp[j].y - vp[i].y * vp[j].x) == 0)
				++j;
			else
			{
				--j;
				break;
			}
		}
		
		// aceeasi panta de la i la j
		for(int k = i; k < j; ++k)
			for(int l = k + 1; l <= j; ++l)
			{
				if(vp[k].i != vp[l].i && vp[k].i != vp[l].j &&
					vp[k].j != vp[l].i && vp[k].j != vp[l].j)
						++res;
			}
		//cout << "[" << i << "," << j << "]" << endl;
		//for(int k = i; k <= j; ++k)
		//	cout << vp[k].i << " " << vp[k]. j << endl;
			
		i = j + 1;
	}
	
	
	out << res << endl;
	
	return 0;
}