Pagini recente » Cod sursa (job #1878858) | Cod sursa (job #36057) | Cod sursa (job #2261836) | Cod sursa (job #1356755) | Cod sursa (job #1048678)
#include <fstream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define EPS 0.0000001
#define INF 1000000000000.0
#define PI 3.14159265359
using namespace std;
int n, vf;
double sol = INF;
struct Punct{int x, y; };
Punct P[100100], St[100100];
struct Punct2{double x, y; };
char *buffer;
long long Dist(Punct A, Punct B)
{
return 1LL * (A.x - B.x) * (A.x - B.x) + 1LL * (A.y - B.y) * (A.y - B.y);
}
double Panta(Punct A, Punct B)
{
return atan2(1.0 * A.y - 1.0 * B.y, 1.0 * A.x - 1.0 * B.x);
}
bool Sortare(Punct A, Punct B)
{
double p1 = Panta(A, P[1]);
double p2 = Panta(B, P[1]);
if(fabs(p1 - p2) < EPS)
return Dist(A, P[1]) < Dist(B, P[1]);
return p1 > p2;
}
long long Intoarcere(Punct A, Punct B, Punct C)
{
return (1LL * A.x * B.y + 1LL * B.x * C.y + 1LL * C.x * A.y - 1LL * C.x * B.y - 1LL * B.x * A.y - 1LL * A.x * C.y);
}
void NextInt(int &x)
{
while(*buffer < '0' || '9' < *buffer)
buffer++;
x = 0;
while('0' <= *buffer && *buffer <= '9')
{
x = x * 10 + *buffer - '0';
buffer++;
}
}
void Read()
{
int i;
ifstream fin("rubarba.in");
fin.seekg(0, ios::end);
int fs = fin.tellg();
fin.seekg(0, ios::beg);
buffer = (char *)malloc(fs);
fin.getline(buffer, fs, 0);
fin.close();
NextInt(n);
for(i = 1; i <= n; ++i)
{
NextInt(P[i].x);
NextInt(P[i].y);
}
}
void MakeItConvex()
{
int i, P0 = 1;
for(i = 2; i <= n; ++i)
if(P[i].y < P[P0].y || (P[i].y == P[P0].y && P[i].x < P[P0].x))
P0 = i;
swap(P[1], P[P0]);
sort(P + 2, P + n + 1, Sortare);
St[++vf] = P[1];
for(i = 2; i <= n; ++i)
{
while(vf >= 2 && Intoarcere(St[vf - 1], St[vf], P[i]) >= 0LL)
vf--;
St[++vf] = P[i];
}
for(i = 1; i <= vf; ++i)
P[i] = St[i];
P[vf + 1] = P[1];
n = vf;
}
Punct2 Rotate(Punct P0, Punct O, double alfa)
{
// roteste in sens trigonometric pe P0 cu alfa radiani in jurul lui O
Punct2 P1;
P1.x = 1.0 * O.x + 1.0 * (P0.x - O.x) * cos(alfa) - 1.0 * (P0.y - O.y) * sin(alfa);
P1.y = 1.0 * O.y + 1.0 * (P0.x - O.x) * sin(alfa) + 1.0 * (P0.y - O.y) * cos(alfa);
return P1;
}
void Solve()
{
int i, j;
double alfa, xmax, xmin, ymax, ymin;
Punct2 newP;
for(i = 1; i <= n; ++i)
{
// iau pe rand fiecare latura a infasuratorii convexe
// ca fiind o latura a bounding-box-ului
alfa = Panta(P[i], P[i + 1]);
xmax = ymax = -INF;
xmin = ymin = INF;
// rotesc punctele in jurul lui P[i]
// ca sa determin mai usor punctele extreme ale bounding-box-ului
for(j = 1; j <= n; ++j)
{
newP = Rotate(P[j], P[i], 2.0 * PI - alfa);
xmax = max(xmax, newP.x);
xmin = min(xmin, newP.x);
ymax = max(ymax, newP.y);
ymin = min(ymin, newP.y);
}
// si sa pot afla astfel aria pentru a actualiza solutia
sol = min(sol, (xmax - xmin) * (ymax - ymin));
}
}
void Write()
{
freopen("rubarba.out", "w", stdout);
printf("%.3lf\n", sol);
}
int main()
{
Read();
MakeItConvex();
Solve();
Write();
return 0;
}