Cod sursa(job #402042)

Utilizator cristiprgPrigoana Cristian cristiprg Data 23 februarie 2010 12:53:41
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define DIM 100005
const int INF = 1<<30;
struct point
{
	int x, y;
} v[DIM];

void swap(point &a, point &b)
{
	point aux = a;
	a = b;
	b = aux;
}

int cmpf(point A, point B)
{
	return (A.x - v[1].x) * (B.y - v[1].y) > (B.x - v[1].x) * (A.y - v[1].y);
}

int n;

void read()
{
	FILE *f = fopen("rubarba.in", "r");
	fscanf(f, "%d", &n);
	point first;
	int ibun = -1;
	first.x = 1<<30, first.y = 1<<30;
	for (int i = 1; i <= n; ++i)
	{
		fscanf(f, "%d%d", &v[i].x, &v[i].y);
		if (v[i].x < first.x)
			first.x = v[i].x, first.y = v[i].y, ibun = i;
		else
			if (v[i].x == first.x)
				if (v[i].y  < first.y)
					first.y = v[i].y, ibun = i;
	}
	fclose(f);
	swap(v[1], v[ibun]);
}

int directie(point A, point B, point C)
{
	int d = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
			
	if (d == 0)//inainte
		return 0;
	if (d < 0)
		return -1;//dreapta
	return 1;//stanga
}

void graham()
{
	int S[DIM], top = 0;
	S[++top] = 1;
	S[++top] = 2;
	for (int i = 3; i <= n; ++i)
	{
		while (directie(v[S[top - 1]], v[S[top]], v[i]) <= 0 && top >= 2)
			--top;
		S[++top] = i;
	}
	n = top;
	for (int i = 1; i <= n; ++i)
		v[i] = v[S[i]];
	
	
}

double dist(point  P1, point P2 , point P) //distanta de la dreapta (P1 P2) la P
{
	return ((P1.y - P2.y) * P.x + (P2.x - P1.x) * P.y + P2.y * P1.x - P1.y * P2.x ) / sqrt((P1.y - P2.y) * (P1.y - P2.y) + (P2.x - P1.x) * (P2.x - P1.x));
}

int cel_mai_din_stanga_al_dreptei(point P1, point P2)
{
	int d,  D = 1, dist_bun = INF, ibun;
	double Dist;
	
	for (int i = 1; i <= n; ++i)
	{
		if (v[i].x != P1.x && v[i].y != P1.y && v[i].x != P2.x && v[i].y != P2.y)
		{
			printf ("i=%d ", i);
			d = directie(P1, P2, v[i]);
			printf ("d=%d ", d);
			if (d > 0 && D == 1)
				D = d, dist_bun = -1;
			Dist = dist(P1, P2, v[i]);
			printf ("dist=%lf\n", Dist);
			
			if (D > 0 && dist_bun < Dist)
				dist_bun = Dist, ibun = i;
				
			if ((D < 0 || D == 0) && dist_bun > Dist)
				dist_bun = Dist, ibun = i;
		}
	}
	printf ("%d\n", D);
	return ibun;
		
}

void solve()
{
	double dmax = -1, d, A, Amin = (double)INF;
	int Pbun = -1, Pstanga, Pdreapta;
	for (int i = 1; i < n; ++i) //pt toate dreptele
	{
		for (int j = 1; j <= n; ++j)
			if (i != j && (i+1) != j) //pt toate celalalte puncte
			{
				d = dist(v[i], v[i+1], v[j]);
				if (d > dmax)
				{
					dmax = d;
					Pbun = j;
				}
			}
		Pstanga = cel_mai_din_stanga_al_dreptei(v[i], v[i+1]);
		
	}
}

int main()
{
	read();
	sort(v + 2, v + n + 1, cmpf);
	graham();
//	solve();
	printf ("%d\n", cel_mai_din_stanga_al_dreptei(v[1], v[5]));
	
	return 0;
}