Cod sursa(job #937244)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 9 aprilie 2013 23:59:00
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.07 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
using namespace std;
#define maxn 100010
#define inf 10000000000000LL
#define inf2 1000010
#define LL long long
#define LD long double

int N;
int S[maxn], varf;
struct Puncte {
	int x, y;
} P[maxn];
struct Pcte {
	long double x, y;
} aux1, aux2, aux3;
double HMAX;

LL Produs(Puncte P1, Puncte P2, Puncte P3) {
	return (LL)P2.x*P3.y - (LL)P2.x*P1.y - (LL)P1.x*P3.y + (LL)P1.x*P1.y - 
		(LL)P3.x*P2.y + (LL)P3.x*P1.y + (LL)P1.x*P2.y - (LL)P1.x*P1.y;
}

int cmp(Puncte a, Puncte b) {
	if((LL)(a.x-P[1].x)*(b.y-P[1].y) != (LL)(b.x-P[1].x)*(a.y-P[1].y)) {
		return (LL)(a.x-P[1].x)*(b.y-P[1].y) > (LL)(b.x-P[1].x)*(a.y-P[1].y);
	}
	else if(P[1].y==a.y && P[1].y==b.y) {
		return (LL)(a.x-P[1].x)*(a.x-P[1].x) + (LL)(a.y-P[1].y)*(a.y-P[1].y) <
			(LL)(b.x-P[1].x)*(b.x-P[1].x) + (LL)(b.y-P[1].y)*(b.y-P[1].y);
	}
	else if(!Produs(a, b, P[1])) {
		return a.x < b.x;
	}
}

void POP() {
	varf--;
}

void PUSH(int a) {
	varf++;
	S[varf]=a;
}

int main() {
	FILE *f1=fopen("rubarba.in", "r"); fstream f2; f2.open("rubarba.out", ios::out);
	int i, j, p, q;
	int xM = inf, yM = inf;

	fscanf(f1, "%d\n", &N);
	for(i=1; i<=N; i++) {
		fscanf(f1, "%d %d\n", &p, &q);
		P[i].x = p; P[i].y = q;
		if(P[i].y < yM) { yM = P[i].y; xM = P[i].x; j=i; }
		else if(P[i].y == yM && P[i].x < xM) { xM = P[i].x; j=i; }
	}
	//infasuratoare convexa
	swap(P[1], P[j]);
	sort(P+2, P+N+1, cmp);

	PUSH(1); PUSH(2);
	for(i=3; i<=N; i++) {
		LL o;
		o=Produs(P[S[varf-1]], P[S[varf]], P[i]);
		if(o==0) { //punctele is coliniare
			PUSH(i);
		}
		else {
			if(o>0) { //intoarcere la stinga - valid
				PUSH(i);
			}
			else { //intoarcere la dreapta - invalid
				while(o<0 && varf>1) {
					POP();
					o=Produs(P[S[varf-1]], P[S[varf]], P[i]);
				}
				PUSH(i);
			}
		}
	}
	int H = varf;
	S[varf + 1] = S[1];
	HMAX = inf;
	for(i=1; i<=H; i++) {
		//panta e data de dreapta (S[i], S[i+1]);
		long double panta, pantaperp;
		long double x, y, x0, y0, x1, y1;
		long double y01, y02;
		panta = 0;
		pantaperp = 0;
		x = y = x0 = y0= x1 = y1 = y01 = y02 = 0;
		if(P[S[i]].x == P[S[i+1]].x && panta == inf) continue;
		else if((LD)(P[S[i+1]].y - P[S[i]].y) / (P[S[i+1]].x - P[S[i]].x) == panta) continue;

		if(P[S[i]].x == P[S[i+1]].x) panta = inf;
		else panta = (LD)(P[S[i+1]].y - P[S[i]].y) / (P[S[i+1]].x - P[S[i]].x);

		//aflu panta perpendicularei
		if(P[S[i]].y == P[S[i+1]].y) pantaperp = inf;
		else pantaperp = - (LD)(P[S[i+1]].x - P[S[i]].x) / (P[S[i+1]].y - P[S[i]].y);

		Puncte susmax = P[S[i]], susmin = P[S[i]];
		Puncte stmax = P[S[i]], drmax = P[S[i]];
		Pcte cstjos, cstsus, cdrjos;

		if(panta == 0 || pantaperp == 0) {
			//caut pctele      
			for(j=1; j<=H; j++) {
				if(P[S[j]].y > susmax.y) {
					susmax = P[S[j]];
				}
				if(P[S[j]].y < susmin.y) {
					susmin = P[S[j]];
				}
			}
			for(j=1; j<=H; j++) {
				if(P[S[j]].x < stmax.x) {
					stmax = P[S[j]];
				}
				if(P[S[j]].x > drmax.x) {
					drmax = P[S[j]];
				}
			}
			cstsus.x = stmax.x;
			cstsus.y = susmax.y;
			cstjos.x = stmax.x;
			cstjos.y = susmin.y;
			cdrjos.x = drmax.x;
			cdrjos.y = susmin.y;
		}
		else {
			x0 = 0;
			y01 = susmax.y - panta*(susmax.x - x0);
			y02 = susmin.y - panta*(susmin.x - x0);
			for(j=1; j<=H; j++) {
				//vad unde intersecteaza axa Oy
				//aflu susmax
				//determin ecuatia dreptei
				//verific daca S[j] se afla deasupra
				aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
				x1 = 0;
				y1 = aux3.y - panta*(aux3.x - x1);
				if(y1 - y01 > 0.00000000) {
					//se afla deasupra
					susmax = P[S[j]];
					y01 = susmax.y - panta*(susmax.x - x0);
				}
				//aflu susmin
				//determin ecuatia dreptei
				aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
				x1 = 0;
				y1 = aux3.y - panta*(aux3.x - x1);
				if(y1 - y02 < 0.00000000) {
					//se afla dedesubt
					susmin = P[S[j]];
					y02 = susmin.y - panta*(susmin.x - x0);
				}
			}

			x0 = 0;
			y01 = stmax.y - pantaperp*(stmax.x - x0);
			y02 = drmax.y - pantaperp*(drmax.x - x0);
			for(j=1; j<=H; j++) {
				//aflu srmax
				//determin ecuatia dreptei
				//verific daca S[j] se afla in stinga
				aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
				x1 = 0;
				y1 = aux3.y - pantaperp*(aux3.x - x1);
				if(y1 - y01 < 0.00000000) {
					//se afla in stinga
					stmax = P[S[j]];
					y01 = stmax.y - pantaperp*(stmax.x - x0);
				}
				//aflu drmax
				//determin ecuatia dreptei
				aux2.x = x0; aux2.y = y0;
				//verific daca S[j] se afla in dreapta
				aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
				x1 = 0;
				y1 = aux3.y - pantaperp*(aux3.x - x1);
				if(y1 - y02 > 0.00000000) {
					//se afla in dreapta
					drmax = P[S[j]];
					y02 = drmax.y - pantaperp*(drmax.x - x0);
				}
			}
			//acum stiu pctele de extrem si pantele dreptelor
			//coltul dreapta jos
			x0 = susmin.x; y0 = susmin.y;
			x1 = drmax.x; y1 = drmax.y;
			cdrjos.x = (x0*panta - y0 + y1 - x1*pantaperp) / (panta - pantaperp);
			cdrjos.y = y0 + (cdrjos.x - x0)*panta;
			//coltul stinga jos
			x0 = susmin.x; y0 = susmin.y;
			x1 = stmax.x; y1 = stmax.y;
			cstjos.x = (x0*panta - y0 + y1 - x1*pantaperp) / (panta - pantaperp);
			cstjos.y = y0 + (cstjos.x - x0)*panta;
			//coltul stinga sus
			x0 = susmax.x; y0 = susmax.y;
			x1 = stmax.x; y1 = stmax.y;
			cstsus.x = (x0*panta - y0 + y1 - x1*pantaperp) / (panta - pantaperp);
			cstsus.y = y0 + (cstsus.x - x0)*panta;
			//calculez aria
		}
		double dist1, dist2;
		dist1 = (cdrjos.x - cstjos.x)*(cdrjos.x - cstjos.x) + (cdrjos.y - cstjos.y)*(cdrjos.y - cstjos.y);
		dist1 = sqrt(dist1);
		dist2 = (LD)(cstsus.x - cstjos.x)*(cstsus.x - cstjos.x) + (LD)(cstsus.y - cstjos.y)*(cstsus.y - cstjos.y);
		dist2 = sqrt(dist2);
		double rasp;
		rasp = (dist1 * dist2);
		//cout<<dist1<<" "<<dist2<<" "<<rasp<<endl;
		HMAX = min(HMAX, rasp);
	}
	//fprintf(f2, "%llf", HMAX);
	//fprintf(f2, "%lf", HMAX);
	f2.setf(ios::fixed,ios::floatfield);
	f2.precision(2);
	f2<<HMAX<<"\n";
	fclose(f1); f2.close();
	return 0;
}