Pagini recente » Cod sursa (job #1762355) | Cod sursa (job #67744)
Cod sursa(job #67744)
using namespace std;
#define MAX_N 255
#define LIM 1<<16
#include <stdio.h>
#include <fstream>
#include <stdlib.h>
FILE *fin=fopen("gradina.in","r"),
*fout=fopen("gradina.out","w");
typedef struct
{
int x;
int y;
} point;
point p[MAX_N];
point p1[MAX_N]; //poligonul lui Ion
point p2[MAX_N]; //poligonul lui Vasile
int stat[MAX_N];
char sol[MAX_N];
int n,n1,n2;
double minn=10000000;
void citire (void)
{
int i;
fscanf(fin,"%d",&n);
for (i=1; i<=n; i++)
fscanf(fin,"%d %d",&p[i].x,&p[i].y);
}
int testconvexity()
{
int i,j,semn=0,a,b,c;
for (i=1; i<=n1; i++)
{
a=p1[i-1].y-p1[i].y;
b=p1[i].x-p1[i-1].x;
c=p1[i-1].x*p1[i].y-p1[i].x*p1[i-1].y;
semn=(a*p1[3].x+b*p1[3].y+c);
for (j=1; j<=n1; j++)
if ((a*p1[j].x+b*p1[j].y+c)*semn<0) return 0;
}
for (i=1; i<=n2; i++)
{
a=p2[i-1].y-p2[i].y;
b=p2[i].x-p2[i-1].x;
c=p2[i-1].x*p2[i].y-p2[i].x*p2[i-1].y;
semn=(a*p2[3].x+b*p2[3].y+c);
for (j=1; j<=n2; j++)
if ((a*p2[j].x+b*p2[j].y+c)*semn<0) return 0;
}
return 1;
}
int testintersection()
{
int i,j,semn=0,a,b,c;
for (i=1; i<=n1; i++)
{
a=p1[i-1].y-p1[i].y;
b=p1[i].x-p1[i-1].x;
c=p1[i-1].x*p1[i].y-p1[i].x*p1[i-1].y;
semn=(a*p2[3].x+b*p2[3].y+c);
for (j=1; j<=n2; j++)
if ((a*p2[j].x+b*p2[j].y+c)*semn<0) return 0;
}
return 1;
}
double arie()
{
int i;
double arie1,arie2,comp;
for (i=1; i<=n1-1; i++)
arie1+=p1[i].x*p1[i+1].y-p1[i+1].x-p1[i].y;
arie1/=2;
for (i=1; i<=n2-1; i++)
arie2+=p2[i].x*p2[i+1].y-p2[i+1].x-p2[i].y;
arie2/=2;
if (arie1>arie2) comp=double(arie1-arie2);
else comp=double (arie2-arie1);
return comp;
}
void solve (void)
{
int d,d1,i,t1,t2,semn,j1,j2;
double comp;
memset(stat,0,sizeof(stat));
for (d=0; d<=LIM; d++)
{
for (d1=1; d1<=n; d1++)
{
semn=rand() % n;
if (stat[semn]==d%2)
if (stat[semn]==1) stat[semn]=0;
else stat[semn]=1;
}
t1=testconvexity();
t2=testintersection();
j1=0; j2=0;
for (i=1; i<=n; i++)
if (stat[i]==1) p1[++j1]=p[i];
else p2[++j2]=p[i];
n1=j1; n2=j2;
if (n1<3 || n2<3) continue;
t1=testconvexity();
t2=testintersection();
if (t1==1 && t2==1)
{
comp=arie();
if (comp<minn)
{
minn=double(comp);
for (i=1; i<=n; i++)
if (stat[i]==1) sol[i]='I'; else sol[i]='V';
}
}
}
fprintf(fout,"%.1f\n",minn);
for (i=1; i<=n; i++)
fprintf(fout,"%c",sol[i]);
}
int main()
{
citire();
solve();
fclose(fin);
fclose(fout);
return 0;
}