Cod sursa(job #2311253)
Utilizator | Data | 2 ianuarie 2019 20:08:27 | |
---|---|---|---|
Problema | Gradina | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 8.52 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
struct Points
{
int x,y,ind;
};
Points v[255];
Points s1[255];
Points s2[255];
Points p1[255];
Points p2[255];
bool sol[255];
bool ans[255];
bool cmp1(Points P1, Points P2)
{
if(P1.x==P2.x)
return P1.y<P2.y;
return P1.x<P2.x;
}
bool cmp2(Points P1, Points P2)
{
if(P1.x==P2.x)
return P1.y>P2.y;
return P1.x<P2.x;
}
long long det(Points P1, Points P2, Points P3)
{
return (P2.x-P1.x)*1LL*(P3.y-P1.y)-(P2.y-P1.y)*1LL*(P3.x-P1.x);
}
long long arie(Points a[], int n)
{
long long ar=0;
Points LL;
LL.x=LL.y=0;
int i;
for(i=2; i<=n; i++)
ar+=det(LL, a[i-1], a[i]);
ar+=det(LL, a[n], a[1]);
return ar;
}
int main()
{ freopen("gradina.in", "r",stdin);
freopen("gradina.out", "w",stdout);
int n,i,j,k,top1,top2,ok,n1,n2;
long long ar1,ar2,minn=1000000000000000000;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d%d", &v[i].x, &v[i].y);
v[i].ind=i;
s1[i]=v[i];
s2[i]=v[i];
}
sort(s1+1, s1+n+1,cmp1);
sort(s2+1, s2+n+1,cmp2);
for(i=1; i<=n; i++){
for(j=i+1; j<=n; j++){
top1=top2=0;
ok=0;
for(k=1; k<=n; k++){
if(det(v[i], v[j], s1[k])>0){
while(top1>=2 && det(p1[top1-1], p1[top1], s1[k])<0)
top1--;
p1[++top1]=s1[k];
}
else{
if(det(v[i], v[j], s1[k])==0){
if(ok==1){
while(top2>=2 && det(p2[top2-1], p2[top2], s1[k])<0)
top2--;
p2[++top2]=s1[k];
}
else{
while(top1>=2 && det(p1[top1-1], p1[top1], s1[k])<0)
top1--;
p1[++top1]=s1[k];
ok=1;
}
}
else{
while(top2>=2 && det(p2[top2-1], p2[top2], s1[k])<0)
top2--;
p2[++top2]=s1[k];
}
}
}
n1=top1;
n2=top2;
ok=0;
for(k=1; k<=n; k++){
if(det(v[i], v[j], s2[k])>0){
while(top1>=n1+2 && det(p1[top1-1], p1[top1], s2[k])>0)
top1--;
p1[++top1]=s2[k];
}
else{
if(det(v[i], v[j], s2[k])==0){
if(ok==1){
while(top2>=n2+2 && det(p2[top2-1], p2[top2], s2[k])>0)
top2--;
p2[++top2]=s2[k];
}
else{
while(top1>=n1+2 && det(p1[top1-1], p1[top1], s2[k])>0)
top1--;
p1[++top1]=s2[k];
ok=1;
}
}
else{
while(top2>=n2+2 && det(p2[top2-1], p2[top2], s2[k])>0)
top2--;
p2[++top2]=s2[k];
}
}
}
if(p1[top1].x==p1[top1-1].x)
top1-=2;
else
top1--;
reverse(p1+n1+1, p1+top1+1);
if(p1[1].ind==p1[top1].ind)
top1--;
if(p2[top2].x==p2[top2-1].x)
top2-=2;
else
top2--;
reverse(p2+n2+1, p2+top2+1);
if(p2[1].ind==p2[top2].ind)
top2--;
if(top1+top2==n){
ar1=arie(p1, top1);
ar2=arie(p2, top2);
ok=0;
if(abs(ar1-ar2)<minn){
minn=abs(ar1-ar2);
for(k=1; k<=top1; k++)
ans[p1[k].ind]=0;
for(k=1; k<=top2; k++)
ans[p2[k].ind]=1;
if(ans[1]==1)
ok=1;
for(k=1; k<=n; k++)
sol[k]=(ans[k]+ok)%2;
}
else
if(abs(ar1-ar2)==minn){
for(k=1; k<=n && sol[k]==(ans[k]+ok)%2; k++);
if(sol[k]>(ans[k]+ok)%2)
for(; k<=n; k++)
sol[k]=(ans[k]+ok)%2;
}
}
top1=top2=0;
ok=1;
for(k=1; k<=n; k++){
if(det(v[i], v[j], s1[k])>0){
while(top1>=2 && det(p1[top1-1], p1[top1], s1[k])<0)
top1--;
p1[++top1]=s1[k];
}
else{
if(det(v[i], v[j], s1[k])==0){
if(ok==1){
while(top2>=2 && det(p2[top2-1], p2[top2], s1[k])<0)
top2--;
p2[++top2]=s1[k];
ok=0;
}
else{
while(top1>=2 && det(p1[top1-1], p1[top1], s1[k])<0)
top1--;
p1[++top1]=s1[k];
}
}
else{
while(top2>=2 && det(p2[top2-1], p2[top2], s1[k])<0)
top2--;
p2[++top2]=s1[k];
}
}
}
n1=top1;
n2=top2;
ok=1;
for(k=1; k<=n; k++){
if(det(v[i], v[j], s2[k])>0){
while(top1>=n1+2 && det(p1[top1-1], p1[top1], s2[k])>0)
top1--;
p1[++top1]=s2[k];
}
else{
if(det(v[i], v[j], s2[k])==0){
if(ok==1){
while(top2>=n2+2 && det(p2[top2-1], p2[top2], s2[k])>0)
top2--;
p2[++top2]=s2[k];
ok=0;
}
else{
while(top1>=n1+2 && det(p1[top1-1], p1[top1], s2[k])>0)
top1--;
p1[++top1]=s2[k];
}
}
else{
while(top2>=n2+2 && det(p2[top2-1], p2[top2], s2[k])>0)
top2--;
p2[++top2]=s2[k];
}
}
}
if(p1[top1].x==p1[top1-1].x)
top1-=2;
else
top1--;
reverse(p1+n1+1, p1+top1+1);
if(p1[1].ind==p1[top1].ind)
top1--;
if(p2[top2].x==p2[top2-1].x)
top2-=2;
else
top2--;
reverse(p2+n2+1, p2+top2+1);
if(p2[1].ind==p2[top2].ind)
top2--;
if(top1+top2==n){
ar1=arie(p1, top1);
ar2=arie(p2, top2);
ok=0;
if(abs(ar1-ar2)<minn){
minn=abs(ar1-ar2);
for(k=1; k<=top1; k++)
ans[p1[k].ind]=0;
for(k=1; k<=top2; k++)
ans[p2[k].ind]=1;
if(ans[1]==1)
ok=1;
for(k=1; k<=n; k++)
sol[k]=(ans[k]+ok)%2;
}
else
if(abs(ar1-ar2)==minn){
for(k=1; k<=n && sol[k]==(ans[k]+ok)%2; k++);
if(sol[k]>(ans[k]+ok)%2)
for(; k<=n; k++)
sol[k]=(ans[k]+ok)%2;
}
}
}
}
if(minn%2==0)
printf("%lld.0\n", minn/2);
else
printf("%lld.5\n", minn/2);
for(i=1; i<=n; i++){
if(sol[i]==0)
printf("I");
else
printf("V");
}
return 0;
}