Pagini recente » Cod sursa (job #1965572) | Cod sursa (job #2856570) | Cod sursa (job #3246566) | Cod sursa (job #159933) | Cod sursa (job #2617265)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream in("rubarba.in");
ofstream out("rubarba.out");
struct nya{double xx,yy;};
nya a[100005];
long long i,n,nr,st[100005],sel[100005],ung[1000005],j;
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;
}