Cod sursa(job #937245)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 9 aprilie 2013 23:59:48
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include<fstream>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<vector>
#include <iostream>
using namespace std;

#define PI pair<int, int>
#define LL long long
#define DB long double
#define x first
#define y second

ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

const int Nmax = 100009;
const DB INF = 10000000000000000000.00;

int N; int K; int StackSize;int Sk;int First;

PI V[Nmax], Stack[Nmax], Convex[Nmax];



inline LL Det(const PI &V1,const PI &V2,const PI &V3){

	return 1LL * V1.x * (V2.y - V3.y)  + 1LL * V2.x * (V3.y - V1.y) + 1LL * V3.x * (V1.y - V2.y);
}


void Read() {

	fin >> N; First = 1;

	for(int i = 1; i <= N; ++i){
		fin >> V[i].x >> V[i].y;
		if(V[i].x < V[First].x || (V[i].x == V[First].x && V[i].y < V[First].y )) First = i;
	}
	swap(V[1], V[First]);
}


inline DB Dist(const PI P ,const DB A, const DB B){

	DB B2 = P.y - A * P.x;
	return (B2 - B)/ sqrt(1 + A * A);
}


void AddConvex(){

	Stack[StackSize = 1] = V[1]; Stack[++StackSize] = V[2];

	for(int i = 3; i <= N; ++i){
		while(StackSize > 1 && Det(Stack[StackSize - 1], Stack[StackSize], V[i]) >= 0LL) StackSize--;
		Stack[++StackSize] = V[i];
	}

	for(int i = 1; i <= StackSize; ++i) Convex[++K] = Stack[i];
}


struct cmp{

	bool operator ()(const PI &P1, const PI &P2)const{
		return Det(V[1], P1, P2) < 0;
	}
};

void ConvexHull(){

	sort(V + 2, V + N + 1, cmp()); AddConvex();
	Convex[K + 1] = Convex[1];
}


DB Tg(const PI &P1, const PI &P2){
	if(P1.x == P2.x)  return INF;

	return  ((DB)P2.y - P1.y) / ((DB)P2.x - P1.x);
}


void DetEcuation(const PI P1,const PI P2, DB &A1, DB &C1, DB &A2, DB &C2){

	A1 = Tg(P1, P2);

	if(A1 == 0) A2 = -INF;
	else A2 = (-1)/ A1;

	DB X = (P1.x + P2.x) / 2.0;DB Y = (P1.y + P2.y) / 2.0;
	C1 = P1.y - A1 * P1.x;
	C2 = Y - A2 * X;//N - ul dreptei perpendiculare pe dreapta(P1, P2)
}


void Solve(){

	DB MinArea = INF;

	if(K <= 1){ fout <<0; return;}

	for(int i = 1; i <= K ; ++i){

		DB A1, A2, C1, C2;
		DB MaxHorizontal = 0.0 ;DB MaxVertical = -INF ; DB MinVertical = INF;

		DetEcuation(Convex[i], Convex[i + 1], A1, C1, A2, C2);
		for(int j = 1 ; j <= K; ++j){

			DB H = fabs(Dist(Convex[j] , A1, C1));

			if(H > MaxHorizontal) MaxHorizontal = H;

			H = Dist(Convex[j], A2, C2);
			if(H > MaxVertical) MaxVertical = H;
			if(H < MinVertical) MinVertical = H;

		}


		cout << setprecision(8);
		cout << "H =\t" << MaxHorizontal << "\n";
		cout << "W =\t" << (MaxVertical - MinVertical) << "\n";

		cout <<fixed << setprecision(2) << MaxHorizontal * (MaxVertical - MinVertical) << "\n";
		if(MinArea > MaxHorizontal * (MaxVertical - MinVertical))
			MinArea = MaxHorizontal * (MaxVertical - MinVertical);

	}
	fout <<fixed << setprecision(2) << MinArea;

}

int main(){

	Read (); ConvexHull (); Solve(); return 0;
}