Cod sursa(job #1052730)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 11 decembrie 2013 19:11:16
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <fstream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define EPS 0.0000001
#define INF 1e50
#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;
 
inline 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);
}
 
inline double Panta(Punct A, Punct B)
{
    return atan2(1.0 * A.y - 1.0 * B.y, 1.0 * A.x - 1.0 * B.x);
}
 
inline 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;
}
 
inline 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);
}
 
inline void NextInt(int &x)
{
    while(*buffer < '0' || '9' < *buffer)
        buffer++;
    x = 0;
    while('0' <= *buffer && *buffer <= '9')
    {
        x = x * 10 + *buffer - '0';
        buffer++;
    }
}
 
inline 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);
    }
}
 
inline 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;
}
 
inline 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));
    }
}
 
inline void Write()
{
    freopen("rubarba.out", "w", stdout);
    printf("%.6lf\n", sol);
}
 
int main()
{
    Read();
    MakeItConvex();
    Solve();
    Write();
    return 0;
}