Cod sursa(job #515505)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 21 decembrie 2010 17:21:49
Problema Trapez Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define inf 3000000000.0
#define NM 1005

int X[NM], Y[NM];

vector <double> pante;

int egale (double n1, double n2)
{
	if (fabs(n1-n2) <= 0.0000001) return 1;
	return 0;
}	

int compara (double n1, double n2)
{
	if (egale(n1, n2)) return 0;
	if (n1 > n2) return 1;
	return -1;
}

int main()
{
	int N, ans = 0;
	
	freopen ("trapez.in", "r", stdin);
	freopen ("trapez.out", "w", stdout);
	
	scanf ("%d", &N);
	
	for (int i = 1; i <= N; ++i) scanf ("%d %d", &X[i], &Y[i]);
	
	for (int i = 1; i <= N; ++i)
		for (int j = i + 1; j <= N; ++j)
		{
			double sus = Y[j] - Y[i];
			double jos = X[j] - X[i];
			
			double m;
			
			if (egale (jos, 0)) m = inf;
			else m = sus/jos;
			
			//printf ("%d %d %lf\n", i, j, m);
			
			pante.push_back(m);
		}	
		
	sort (pante.begin(), pante.end());

	/*
	for (int i = 0; i < pante.size(); ++i) printf ("%lf ", pante[i]);
	printf ("\n");
	*/
	
	for (int i = 1; i <= N; ++i)
		for (int j = i + 1; j <= N; ++j)
		{
			double sus = Y[j] - Y[i];
			double jos = X[j] - X[i];
			
			double m;
			
			if (egale (jos, 0)) m = inf;
			else m = sus/jos;
			
			int prim, ultim;
			
			// prima valoare egala cu m
			
			int st = 0, dr = pante.size() - 1;
			
			while (st < dr)
			{
				int mij = (st + dr)/2;
				
				if (compara(m, pante[mij]) <= 0) dr = mij;
				else st = mij + 1;
			}	
			
			prim = st;
			
			// ultima valoare egala cu m
			
			st = 0, dr = pante.size() - 1;
			
			while (st < dr - 1)
			{
				int mij = (st + dr)/2;
				
				if (compara(m, pante[mij]) >= 0) st = mij;
				else dr = mij - 1;
			}	
			
			if (egale (m, pante[dr])) st = dr;
			
			ultim = st;
			
			//printf ("%d %d %d %d\n", i, j, prim, ultim);
			
			ans += (ultim - prim); 
		}	
		
	printf ("%d", ans/2);	
	
	return 0;
}