Cod sursa(job #397363)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 16 februarie 2010 20:32:53
Problema Trapez Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define N 1000
#define ll long long
#define INF -1234562
#define double long double 

typedef struct { ll x, y; char negativ; double dp; } panta;

typedef struct { ll x, y; } punct;

punct puncte[N + 1];
panta v[N * N + 1];
ll n, contorTrapeze, dimv;
ll ndpx = -1;

void citeste()
{
	scanf("%lld", &n);
	int i;
	for(i = 0; i < n; ++i) scanf("%lld%lld", &(puncte[i].x), &(puncte[i].y));
}

void calculeazaPante()
{
	int i, j, indexPanta = 0;
	for(i = 0; i < n; ++i)
	{
		for(j = i + 1; j < n; ++j)
		{
//			if(i != j)
//			{
//				v[indexPanta].x = puncte[i].x - puncte[j].x;
//				v[indexPanta].y = puncte[i].y - puncte[j].y;
//				
//				if(v[indexPanta].x < 0 && v[indexPanta].y < 0)
//				{
//					v[indexPanta].x = -v[indexPanta].x;
//					v[indexPanta].y = -v[indexPanta].y;
//				}
//				
				if(puncte[i].x == puncte[j].x) v[indexPanta].dp = INF;
				else v[indexPanta].dp = (double)((double)(puncte[i].y - puncte[j].y) / (double)(puncte[i].x - puncte[j].x));
			
				indexPanta++;
				
//				if(v[indexPanta].x < 0 || v[indexPanta].y < 0) v[indexPanta].negativ = 1;
//				else v[indexPanta].negativ = 0;
				
//			}
		}
	}
	dimv = indexPanta;
}

int fcmp(const void* a, const void* b)
{
	panta pa, pb;
	pa = *((panta*)a);
	pb = *((panta*)b);
	if(pa.dp < pb.dp) return -1;
	else return 1;
//	if(pa.negativ && (!pb.negativ)) return -1;
//	if((!pa.negativ) && pb.negativ) return 1;
//	ll npa = pa.y * pb.x;
//	ll npb = pb.y * pa.x;
//	if(npa < npb) return -1;
//	else return 1;
}

void sorteazaPante()
{
	qsort(v, dimv, sizeof(panta), fcmp);
}

void numaraTrapeze()
{
	int offset = 0, depl, neg;
	while(offset < dimv - 1)
	{
		depl = 1;
		neg = 0;
		while(fabs(v[offset].dp - v[offset + depl].dp) < 1E-14)
		{	
			depl++;
			neg++;
		}
		if(neg > 2) exit(0);
		offset += depl;
	}
}

void scrieRezultat()
{
	printf("%lld\n", contorTrapeze);
}

int main()
{
	freopen("trapez.in", "r", stdin);
	freopen("trapez.out", "w", stdout);
	citeste();
	calculeazaPante();
	sorteazaPante();
	numaraTrapeze();
	scrieRezultat();
	return 0;
}