Pagini recente » Cod sursa (job #713052) | Cod sursa (job #1277295) | Cod sursa (job #232389) | Cod sursa (job #725856) | Cod sursa (job #133731)
Cod sursa(job #133731)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define inf 10000
using namespace std;
long n,x[256],y[256],i,j,k,p,q,poz;
long v1[256],v2[256],t;
long long E;
vector <int>st;
double amin=inf,a1,a2;
long isLeft (long n0,long n1,long n2){
if ((long long)(x[n1]-x[n0])*(y[n2]-y[n0])-(x[n2]-x[n0])*(y[n1]-y[n0])<0)
return -1;
else return 1;
}
int comp1(const void *n1,const void *n2){
return -isLeft(v1[0],*((long*)n1),*((long*)n2));
}
int comp2(const void *n1,const void *n2){
return -isLeft(v2[0],*((long*)n1),*((long*)n2));
}
int main(){
freopen("gradina.in","r",stdin);
freopen("gradina.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=n;i++)
scanf("%ld %ld",&x[i],&y[i]);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
if (i!=j){
p=1;q=1;
v1[1]=i;v2[1]=j;
for (k=1;k<=n;k++)
if (k!=i&&k!=j){
E=(long long)(x[k]-x[i])*(y[j]-y[i])-(y[k]-y[i])*(x[j]-x[i]);
if (E<0)v1[++p]=k;
else v2[++q]=k;
}
if (p==1||q==1)continue;
//primul poligon
poz=1;
for (k=1;k<=p;k++)
if (y[v1[k]]<y[v1[poz]])
poz=k;
else if (y[v1[k]]==y[v1[poz]])
if (x[v1[k]]>x[v1[poz]])poz=k;
v1[0]=v1[poz];
v1[poz]=v1[p];
qsort(v1+1,p-1,sizeof(long),comp1);
//Graham Scan
st.clear();
st.push_back(v1[0]);
st.push_back(v1[1]);
k=2;
while (k<p){
t=st.size()-1;
if (t>0)
if (isLeft(st[t-1],st[t],v1[k])==1){
st.push_back(v1[k]);
k++;
}
else st.pop_back();
}
a1=0;
for (k=0;k<st.size()-1;k++){
a1+=x[st[k]]*y[st[k+1]];
a1-=x[st[k+1]]*y[st[k]];
}
a1+=x[st[k]]*y[st[0]];
a1-=x[st[0]]*y[st[k]];
//for (k=0;k<st.size();k++)
// printf("%d ",st[k]);
//printf("\n");
//al doilea poligon
poz=1;
for (k=1;k<=q;k++)
if (y[v2[k]]<y[v2[poz]])
poz=k;
else if (y[v2[k]]==y[v2[poz]])
if (x[v2[k]]>x[v2[poz]])poz=k;
v2[0]=v2[poz];
v2[poz]=v2[q];
qsort(v2+1,q-1,sizeof(long),comp2);
//Graham Scan
st.clear();
st.push_back(v2[0]);
st.push_back(v2[1]);
k=2;
while (k<q){
t=st.size()-1;
if (t>0)
if (isLeft(st[t-1],st[t],v2[k])==1){
st.push_back(v2[k]);
k++;
}
else st.pop_back();
}
a2=0;
for (k=0;k<st.size()-1;k++){
a2+=x[st[k]]*y[st[k+1]];
a2-=x[st[k+1]]*y[st[k]];
}
a2+=x[st[k]]*y[st[0]];
a2-=x[st[0]]*y[st[k]];
if (a1>a2){
if (a1-a2<amin)amin=a1-a2;
}
else if (a2-a1<amin)amin=a2-a1;
//for (k=0;k<st.size();k++)
// printf("%d ",st[k]);
//printf("\n");
}
}
printf("%.2lf\n",amin/2.0);
return 0;
}