Cod sursa(job #1061506)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 19 decembrie 2013 21:29:23
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 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],a,b,U1,U2;
bitset<NMAX> viz; long long SOL; char T[NMAX];
struct Point {int X,Y,I;} P[NMAX],A[NMAX],B[NMAX];
bool cmp(Point A,Point B)
{
    if(A.X==B.X) return A.Y<B.Y;
    return A.X<B.X;
}
long long CrossProduct(Point A,Point B,Point C)
{
    return 1LL*A.X*B.Y+1LL*B.X*C.Y+1LL*C.X*A.Y-1LL*B.Y*C.X-1LL*A.Y*B.X-1LL*C.Y*A.X;
}
void ConvexHull(Point P[NMAX],int N,int H[NMAX],int &M)
{
    int i; M=0; viz=0;
    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;
    for(int 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;
    return S;
}
void Update()
{
    if(U1+U2<N) return; int i; char S[NMAX];
    for(i=1;i<=U1;i++) S[A[H1[i]].I]='I';
    for(i=1;i<=U2;i++) S[B[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(A,H1,U1)-Area(B,H2,U2);
    if(X<0) X=-X;
    if(X<SOL || (X==SOL && strcmp(S+1,T+1)<0))
        {SOL=X;strcpy(T+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",&P[i].X,&P[i].Y);
        P[i].I=i;
    }
    sort(P+1,P+N+1,cmp);
    for(i=1;i<=N;i++)
        for(j=i+1;j<=N;j++)
        {
            a=0; A[++a]=P[i];
            b=0; B[++b]=P[j];
            for(k=1;k<=N;k++)
                if(k!=i && k!=j)
                {
                    if(CrossProduct(P[i],P[j],P[k])<0) A[++a]=P[k];
                    else B[++b]=P[k];
                }
            if(a>=3 && b>=3)
            {
                ConvexHull(A,a,H1,U1);
                ConvexHull(B,b,H2,U2);
                //Update();
            }

            a=0; A[++a]=P[j];
            b=0; B[++b]=P[i];
            for(k=1;k<=N;k++)
                if(k!=i && k!=j)
                {
                    if(CrossProduct(P[i],P[j],P[k])<0) A[++a]=P[k];
                    else B[++b]=P[k];
                }
            if(a>=3 && b>=3)
            {
                //ConvexHull(A,a,H1,U1);
                //ConvexHull(B,b,H2,U2);
                //Update();
            }
        }
    printf("%f\n",SOL/2.0); printf("%s\n",T+1);
    return 0;
}