Cod sursa(job #133731)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 9 februarie 2008 16:39:12
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.78 kb
#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;
}