Cod sursa(job #2403655)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 11 aprilie 2019 19:15:13
Problema Rubarba Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
const double eps=1e-14;
const double PI=2.0*acos(0.0);
vector <pair<int,int>> v;
pair<int,int> ll;
int top;
int st[100005];
double cp(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
    return (b.first-a.first)*(c.second-b.second)-(b.second-a.second)*(c.first-b.first);
}
int ccw(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
    double val=cp(a,b,c);
    if(fabs(val)<eps)return 0;
    if(val>=eps)return 1;
    return -1;
}
bool cmp(pair<int,int> a,pair<int,int> b)
{
    return ccw(ll,a,b)==1;
}
double ans(double angle)
{
    double s=sin(angle),c=cos(angle),ax,ay;
    double a1=1e6,b1=1e6,a2=1e-6,b2=1e-6;
    int i;
    for(i=0;i<top;++i)
    {
        ax=1.0*v[st[i]].first*c+1.0*v[st[i]].second*s;
        ay=(-1.0)*v[st[i]].first*s+1.0*v[st[i]].second*c;
        if(ax<a1)a1=ax;
        if(ax>a2)a2=ax;
        if(ay<b1)b1=ay;
        if(ay>b2)b2=ay;
    }
    return fabs((a1-a2)*(b1-b2));
}
int main()
{
    freopen("rubarba.in","r",stdin);
    freopen("rubarba.out","w",stdout);
    int n,i,a,b,val;
    scanf("%d",&n);
    for(i=0;i<n;++i)
    {
        scanf("%d%d",&a,&b);
        v.push_back(make_pair(a,b));
        if(v[i].second<v[0].second)
            swap(v[0],v[i]);
        else
            if(v[i].second==v[0].second)
            {
                if(v[i].first>v[0].first)
                    swap(v[i],v[0]);
            }
    }
    ll=v[0];
    sort(v.begin()+1,v.end(),cmp);
    v.push_back(v[0]);
    st[0]=0;st[1]=1;
    i=2;top=2;
    while(i<v.size())
    {
        val=ccw(v[st[top-1]],v[st[top]],v[i]);
        if(val>=0)
        {
            if(val==1)
                st[++top]=i;
            ++i;
        }
        else
            --top;
    }
    double ang,sol=1e12,aux;
    for(ang=0;ang-2*PI<eps;ang+=1e-4)
    {
        aux=ans(ang);
        if(sol-aux>eps)
            sol=aux;
    }
    printf("%.2f",sol);
    return 0;
}