Cod sursa(job #1061563)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 19 decembrie 2013 22:07:50
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<cstring>
using namespace std;
const int NMAX = 255;
int i,j,k,N,H1[NMAX],H2[NMAX],I,J,U1,U2;
bool viz[NMAX]; long long sol; char SOL[NMAX];
struct Point {int X,Y,I;} V[NMAX],P[NMAX],Q[NMAX];
bool cmp(Point A,Point B)
{
    if(A.X==B.X) return A.Y<B.Y;
    return A.X<B.X;
}
int CrossProduct(Point A,Point B,Point C)
{
    return (B.X-A.X)*(C.Y-A.Y)-(B.Y-A.Y)*(C.X-A.X);
}
void ConvexHull(Point P[NMAX],int N,int H[NMAX],int &M)
{
    int i; M=0; memset(viz,0,sizeof(viz));
    for(i=1;i<=N;i++)
    {
        while(M>=2 && CrossProduct(P[H[M-1]],P[H[M]],P[i])>0) M--;
        H[++M]=i;
    }
    for(i=1;i<=M;i++) viz[H[i]]=1; viz[H[1]]=0;
    for(i=N;i;i--)
        if(!viz[i])
        {
            while(M>=2 && CrossProduct(P[H[M-1]],P[H[M]],P[i])>0) M--;
            H[++M]=i;
        }
        M--;
}
long long Area(Point P[NMAX],int H[NMAX],int M)
{
    long long S=0; int i;
    for(i=1;i<=M;i++)
        S+=1LL*P[H[i]].X*P[H[i+1]].Y-1LL*P[H[i]].Y*P[H[i+1]].X;
    if(S<0) S=-S;
    return S;
}
void Update()
{
    if(U1+U2<N) return; int i; char S[NMAX];
    for(i=1;i<=U1;i++) S[P[H1[i]].I]='I';
    for(i=1;i<=U2;i++) S[Q[H2[i]].I]='V';
    if(S[1]=='V')
        for(i=1;i<=N;i++)
            if(S[i]=='V') S[i]='I';
            else S[i]='V';
    long long X=Area(P,H1,U1)-Area(Q,H2,U2);
    if(X<0) X=-X;
    if(X<sol || (X==sol && strcmp(S+1,SOL+1)<0))
        {sol=X; strcpy(SOL+1,S+1);}
}
int main()
{
    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);
    scanf("%d",&N); sol=1LL<<62;
    for(i=1;i<=N;i++)
    {
        scanf("%d%d",&V[i].X,&V[i].Y);
        V[i].I=i;
    }
    sort(P+1,P+N+1,cmp);
    for(i=1;i<=N;i++)
        for(j=i+1;j<=N;j++)
        {
            I=J=0;
            for(k=1;k<=N;k++)
                {
                    if(k==i) {P[++I]=V[k]; continue;}
                    if(k==j) {Q[++J]=V[k]; continue;}
                    if(CrossProduct(V[i],V[j],V[k])<0) P[++I]=V[k];
                    else Q[++J]=V[k];
                }
            if(I>=3 && J>=3)
            {
                ConvexHull(P,I,H1,U1);
                ConvexHull(Q,J,H2,U2);
                Update();
            }

            I=J=0;
            for(k=1;k<=N;k++)
                {
                    if(k==j) {P[++I]=V[k]; continue;}
                    if(k==i) {Q[++J]=V[k]; continue;}
                    if(CrossProduct(V[i],V[j],V[k])<0) P[++I]=V[k];
                    else Q[++J]=V[k];
                }
            if(I>=3 && J>=3)
            {
                ConvexHull(P,I,H1,U1);
                ConvexHull(Q,J,H2,U2);
                Update();
            }
        }
    printf("%.1lf\n",sol/2.0); //printf("%s\n",SOL+1);
    return 0;
}