Cod sursa(job #2617553)

Utilizator Savu_Stefan_CatalinSavu Stefan Catalin Savu_Stefan_Catalin Data 21 mai 2020 22:55:41
Problema Rubarba Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream in("rubarba.in");
ofstream out("rubarba.out");
struct nya{long double xx,yy;};
nya a[100005];
long long  i,n,nr,st[100005],sel[100005],ung[1000005],j;
long double mi,un1,un2,ii,jj,jj1,jj2;
int cmp(nya a,nya b)
{
    return make_pair(a.xx,a.yy)<make_pair(b.xx,b.yy);
}
double det(nya a,nya b,nya c)
{
    return a.xx*b.yy+b.xx*c.yy+a.yy*c.xx-b.yy*c.xx-a.yy*b.xx-a.xx*c.yy;
}
int main()
{
    in>>n;
    for (i=1;i<=n;++i)
    {
        in>>a[i].xx>>a[i].yy;
    }
    sort(a+1,a+n+1,cmp);
    st[1]=1;
    st[2]=2;
    nr=2;
    for (i=3;i<=n;++i)
    {
        while (nr>1&&det(a[st[nr-1]],a[st[nr]],a[i])>=0)
        {
            sel[st[nr]]=0;
            nr--;
        }
        sel[i]=1;
        st[++nr]=i;
    }
    for (i=n;i>=1;--i)
    {
        if (sel[i]==0)
        {
        while (nr>1&&det(a[st[nr-1]],a[st[nr]],a[i])>=0)
        {
            sel[st[nr]]=0;
            nr--;
        }
        sel[i]=1;
        st[++nr]=i;
        }
    }
    nr--;
    st[0]=st[nr];
    st[nr+1]=st[1];
    for (i=1;i<=nr;++i)
        {
            un1=(atan2(a[st[i]].yy-a[st[i-1]].yy,a[st[i]].xx-a[st[i-1]].xx)+2*acos(-1))*180/acos(-1);
            un1=int(un1*1000);
            un2=(atan2(a[st[i+1]].yy-a[st[i]].yy,a[st[i+1]].xx-a[st[i]].xx)+2*acos(-1))*180/acos(-1);
            un2=int(un2*1000);
            un1=int(un1)%360000;
            un2=int(un2)%360000;
            j=un1;
            while (j!=un2){
                ung[j]=i;
                j=(j+359999)%360000;
                }
        }
        mi=1000000000000000000;
    for (i=0;i<=89999;++i)
    {
        ii=i;
        ii=ii/1000;
        jj1=abs((a[st[ung[i+90000]]].yy-a[st[ung[i+180000+90000]]].yy)*(sin((ii+90000)*acos(-1)/180))+(a[st[ung[i+90000]]].xx-a[st[ung[i+180000+90000]]].xx)*(cos((ii+90000)*acos(-1)/180)));
        jj2=abs((a[st[ung[i]]].yy-a[st[ung[i+180000]]].yy)*(cos(ii*acos(-1)/180))-(a[st[ung[i]]].xx-a[st[ung[i+180000]]].xx)*(sin(ii*acos(-1)/180)));
        jj=jj1*jj2;
        mi=min(mi,jj);

    }
    out<<fixed<<setprecision(2)<<mi;
    return 0;
}