Cod sursa(job #1358144)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 24 februarie 2015 13:34:04
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.67 kb
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#define pb push_back
#define infinite 100001
#define PI 3.14159265359
using namespace std;

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

typedef struct{
    int id;
    long double x;
    long double y;
}Point;

typedef struct{
    double angle;
    Point P;
}C;

bool pointsort(Point A, Point B)
{
    return (A.x<B.x||(A.x==B.x && A.y<B.y));
}

double ccw(Point O, Point A, Point B)
{
    return (A.x-O.x)*(B.y-O.y) - (A.y-O.y)*(B.x-O.x);
}

double angle(Point A, Point B)
{    
    if(B.x==A.x) return PI/2;
    double r=atan((B.y-A.y)/(B.x-A.x));
    return r<0?PI+r:r;
}

vector <Point> P;
C Caliper[5];
int n;

int main() {
    
    fin>>n;
    for(int i=0; i<n; ++i)
    {
        Point A;
        fin>>A.x>>A.y;
        P.pb(A);
    }
    
    sort(P.begin(), P.end(), pointsort);
    
    vector <Point> H(n*2);
    int k=0;
    for(int i=0; i<n; ++i)
    {
        while(k>=2 && ccw(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }
    for(int i=n-2,t=k+1; i>=0; i--)
    {
        while(k>=t && ccw(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }
    k--;
    for(int i=1; i<=k; ++i) // Dam id-uri pentru rotatii
        H[i].id=i;
    /*
    for(int i=1; i<=k; ++i)
        fout<<H[i].id<<" "<<H[i].x<<" "<<H[i].y<<"\n";
    */
    
    Caliper[1].P.x=Caliper[3].P.y=infinite;
    for(int i=1; i<=k; ++i){
        if(H[i].x<Caliper[1].P.x) Caliper[1].P=H[i];
        if(H[i].x>Caliper[2].P.x) Caliper[2].P=H[i];
        if(H[i].y<Caliper[3].P.y) Caliper[3].P=H[i];
        if(H[i].y>Caliper[4].P.y) Caliper[4].P=H[i];
    }
    
    double trotation=0;
    double amin=infinite;
    Caliper[1].angle=Caliper[2].angle=PI/2;
    Caliper[3].angle=Caliper[4].angle=0;
    double dist12 = sqrt(pow(Caliper[1].P.x-Caliper[2].P.x,2) + pow(Caliper[1].P.y-Caliper[2].P.y,2));
    double dist34 = sqrt(pow(Caliper[3].P.x-Caliper[4].P.x,2) + pow(Caliper[3].P.y-Caliper[4].P.y,2));
    double area=dist12*sin(abs(angle(Caliper[1].P, Caliper[2].P)-Caliper[1].angle))*dist34*sin(abs(angle(Caliper[3].P, Caliper[4].P)-Caliper[3].angle));
    amin=area;
    while(trotation<PI/2)
    {
        fout<<setprecision(2)<<fixed;
        /*
        fout<<"rotation: \n";
        fout<<"Caliper 1: "<<Caliper[1].P.id<<" "<<Caliper[1].angle<<"\n";
        fout<<"Caliper 2: "<<Caliper[2].P.id<<" "<<Caliper[2].angle<<"\n";
        fout<<"Caliper 3: "<<Caliper[3].P.id<<" "<<Caliper[3].angle<<"\n";
        fout<<"Caliper 4: "<<Caliper[4].P.id<<" "<<Caliper[4].angle<<"\n";
        */
        double dmin=180;
        int cmin;
        for(int i=1; i<=4; ++i)
        {
            double delta=abs(angle(Caliper[i].P, H[(Caliper[i].P.id<k)?Caliper[i].P.id+1:1])-Caliper[i].angle);
            if(delta<dmin){
                dmin=delta;
                cmin=i;
            }
        }
        //fout<<"rotation by "<<dmin<<"\n";
        for(int i=1; i<=4; ++i)
            Caliper[i].angle+=dmin;
        
        Caliper[cmin].P=H[(Caliper[cmin].P.id<k)?Caliper[cmin].P.id+1:1];
        
        double dist12 = sqrt(pow(Caliper[1].P.x-Caliper[2].P.x,2) + pow(Caliper[1].P.y-Caliper[2].P.y,2));
        double dist34 = sqrt(pow(Caliper[3].P.x-Caliper[4].P.x,2) + pow(Caliper[3].P.y-Caliper[4].P.y,2));
        double area=dist12*sin(abs(angle(Caliper[1].P, Caliper[2].P)-Caliper[1].angle))*dist34*sin(abs(angle(Caliper[3].P, Caliper[4].P)-Caliper[3].angle));
        //fout<<"current area :"<<area<<"\n";
        if(area<amin)
            amin=area;
        trotation+=dmin;
    }
    fout<<amin;

}