Pagini recente » Cod sursa (job #3151006) | Cod sursa (job #2173399) | Cod sursa (job #89548) | Cod sursa (job #1991373) | Cod sursa (job #713791)
Cod sursa(job #713791)
#include <cstdio>
#include <algorithm>
#include <cfloat>
#include <cmath>
#define MAXN 100001
using namespace std;
int n, coord[MAXN][2], points[MAXN], btLeft;
int ch[MAXN];
bool compare(const int &a, const int &b)
{
return (coord[a][0] - coord[btLeft][0]) * (coord[b][1] - coord[btLeft][1])
> (coord[a][1] - coord[btLeft][1]) * (coord[b][0] - coord[btLeft][0]);
}
bool ccwTurn(int p1, int p2, int p3)
{
return (coord[p2][0] - coord[p1][0]) * (coord[p3][1] - coord[p1][1]) > (coord[p2][1] - coord[p1][1]) * (coord[p3][0] - coord[p1][0]);
}
void convex_hull();
void solve();
int main()
{
freopen("rubarba.in", "r", stdin);
freopen("rubarba.out","w",stdout);
scanf("%d", &n);
coord[btLeft][0] = coord[btLeft][1] = 0x7fffffff;
for (int i = 1 ; i <= n ; ++i)
{
scanf("%d %d", &coord[i][0], &coord[i][1]);
if (coord[i][1] < coord[btLeft][1] || (coord[i][1] == coord[btLeft][1] && coord[i][0] < coord[btLeft][0]))
btLeft = i;
}
convex_hull();
solve();
return 0;
}
void convex_hull()
{
for (int i = 1 ; i <= n ; ++i)
if (i != btLeft)
points[++points[0]] = i;
sort(points + 1, points + points[0] + 1, compare);
ch[0] = 3;
ch[1] = btLeft;
ch[2] = points[1];
ch[3] = points[2];
for (int i = 3 ; i <= points[0] ; ++i)
{
while (!ccwTurn(ch[ch[0] - 1], ch[ch[0]], points[i]))
ch[0]--;
ch[++ch[0]] = points[i] ;
}
}
void solve()
{
double minarea = DBL_MAX;
ch[ch[0] + 1] = ch[1];
for (int i = 1 ; i <= ch[0] ; ++i)
{
double vx = coord[ch[i + 1]][0] - coord[ch[i]][0];
double vy = coord[ch[i + 1]][1] - coord[ch[i]][1];
double len = sqrt(vx * vx + vy * vy);
vx /= len;vy /= len;
double px = vy, py = -vx;
double s0 = 0, s1 = 0, t0 = 0, t1 = 0;
for (int j = 1 ; j <= ch[0] ; ++j)
{
int ux = coord[ch[j]][0] - coord[ch[i]][0];
int uy = coord[ch[j]][1] - coord[ch[i]][1];
double test = ux * vx + uy * vy;
if (test < s0) s0 = test;
else if (test > s1) s1 = test;
test = ux * px + uy * py;
if (test < t0) t0 = test;
else if (test > t1) t1 = test;
}
double area = (s1 - s0) * (t1 - t0);
if (area < minarea)
minarea = area;
}
printf("%.2f\n", minarea);
}