Pagini recente » Cod sursa (job #1093915) | Cod sursa (job #1370685) | Cod sursa (job #3303) | Cod sursa (job #559021) | Cod sursa (job #920118)
Cod sursa(job #920118)
#include<fstream>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<vector>
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 double INF = 10000000000.00;
int N; int K; int StackSize;int Sk;
PI V[Nmax], Stack[Nmax], Convex[Nmax];
double Horizontal, Vetrtical, Ans;
LL Det(const PI P1,const PI P2,const PI P3){
return 1LL * (P2.x - P1.x) * (P3.y - P1.y) - 1LL * (P3.x - P1.x) * (P2.y - P1.y);
}
void Read() {
fin >> N;
for(int i = 1; i <= N; ++i)
fin >> V[i].x >> V[i].y;
}
inline long double Dist(const PI P ,const DB A, const DB B, const DB C){ return (P.x * A + P.y * B + C)/ sqrt(B * B + A * A);}
void AddConvex(){
StackSize = 1;
Stack[StackSize] = 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];
if(Sk == 0) Convex[2 * K + 1] = Stack[1];
}
bool cmp2(const PI P1, const PI P2){
return (P1.y > P2.y )|| ((P1.y == P2.y) && (P1.x > P2.x));
}
bool cmp(const PI P1, const PI P2){
return (P1.y < P2.y )|| ((P1.y == P2.y) && (P1.x < P2.x));
}
void ConvexHull(){
sort(V + 1, V + N + 1, cmp); AddConvex(); Sk = K;
sort(V + 1, V + N + 1, cmp2); AddConvex();
}
double Tg(const PI &P1, const PI &P2){
if(P1.x == P2.x) return INF;
return (P1.y - P2.y) / (P1.x - P2.x);
}
void DetEcuation(const PI P1,const PI P2, DB &A1,DB &B1, DB &C1, DB &A2, DB &B2, DB &C2){
A1 = Tg(P1, P2);
if(A1 == 0) A2 = -INF;
else A2 = -1/ A1;
B1 = B2 = -1;
C1 = P1.y - A1 * P1.x;
DB X = (P1.x + P2.x) / 2;DB Y = (P1.y + P2.y) / 2;
C2 = Y - A2 * X;
}
void Solve(){
double long MinArea = INF;
for(int i = 1; i <= Sk; ++i){
long double A1, B1, C1, A2, B2, C2;
double long MaxHorizontal = 0.0 ;DB MaxVertical = 0.0 ; DB MinVertical = 0.0;
DetEcuation(Convex[i], Convex[i + 1], A1, B1, C1, A2, B2, C2);
for(int j = i ; j <= i + Sk - 1; ++j){
//fout << Convex[j].x <<" " << Convex[j].y <<'\n';
DB H = fabs(Dist(Convex[j], A1, B1, C1));
DB V1 = Dist(Convex[j], A2, B2, C2);
if(H > MaxHorizontal) MaxHorizontal = H;
if(V1 > MaxVertical) MaxVertical = V1;
if(V1 < MinVertical) MinVertical = V1;
}
if(MinArea > MaxHorizontal * (MaxVertical - MinVertical))
MinArea = MaxHorizontal * (MaxVertical - MinVertical);
}
fout <<fixed << setprecision(2) << MinArea;
}
int main(){
Read (); ConvexHull (); Solve(); return 0;
}