Pagini recente » Cod sursa (job #297327) | Cod sursa (job #2617606) | Cod sursa (job #2944973) | Cod sursa (job #1774275) | Cod sursa (job #487035)
Cod sursa(job #487035)
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define MAXN 260
using namespace std;
int N,NPlanePoints,NStack;
struct point{
int x,y,nr;
} Points[MAXN];
int PlanePoints[MAXN];
int PointsStack[MAXN];
long long mindiffarea;
int Solution[MAXN],PartSol[MAXN];
bool DefArea;
inline bool RightTurn(int p1,int p2,int p3){
int x1=Points[p1].x-Points[p2].x;
int x2=Points[p3].x-Points[p2].x;
int y1=Points[p1].y-Points[p2].y;
int y2=Points[p3].y-Points[p2].y;
long long product=(long long)x1*(long long)y2-(long long)x2*(long long)y1;
if (product<0) return false; else return true;
}
inline bool cmp(const point &A, const point &B){
if (A.x!=B.x) return (A.x<B.x); else
return (A.y<B.y);
}
inline bool LessThan(){
for (int i=1;i<=N;++i)
if (PartSol[i]<Solution[i]) return true; else
if (PartSol[i]>Solution[i]) return false;
return false;
}
long long HullArea(){
NStack=2;
PointsStack[1]=PlanePoints[1];
PointsStack[2]=PlanePoints[2];
for (int i=3;i<=NPlanePoints;++i){
PointsStack[++NStack]=PlanePoints[i];
while (NStack>=3 && RightTurn(PointsStack[NStack-2],PointsStack[NStack-1],PointsStack[NStack])){
PointsStack[NStack-1]=PointsStack[NStack];
--NStack;
}
}
PointsStack[++NStack]=PlanePoints[NPlanePoints-1];
for (int i=NPlanePoints-2;i>=1;--i){
PointsStack[++NStack]=PlanePoints[i];
while (NStack>=3 && RightTurn(PointsStack[NStack-2],PointsStack[NStack-1],PointsStack[NStack])){
PointsStack[NStack-1]=PointsStack[NStack];
--NStack;
}
}
if ((NStack-1) != NPlanePoints) return -1;
long long area=0;
for (int i=1;i<NStack;++i)
area+=((long long)Points[PointsStack[i]].x+Points[PointsStack[i+1]].x)*
((long long)Points[PointsStack[i+1]].y-Points[PointsStack[i]].y);
return area;
}
void Split(int p1,int p2){
long long A=Points[p1].y-Points[p2].y;
long long B=Points[p2].x-Points[p1].x;
long long C=(long long)Points[p1].x*Points[p2].y-(long long)Points[p2].x*Points[p1].y;
NPlanePoints=0;
for (int i=1;i<=N;++i)
if (i!=p2)
if (i==p1 || (A*Points[i].x+B*Points[i].y+C)<0)
PlanePoints[++NPlanePoints]=i;
if (NPlanePoints<3 || (N-NPlanePoints)<3) return ;
long long FirstArea=HullArea();
if (FirstArea==-1) return ;
NPlanePoints=0;
for (int i=1;i<=N;++i)
if (i!=p1)
if (i==p2 || (A*Points[i].x+B*Points[i].y+C)>0)
PlanePoints[++NPlanePoints]=i;
long long SecondArea=HullArea();
if (SecondArea==-1) return ;
long long DiffArea=FirstArea-SecondArea;
if (DiffArea<0) DiffArea=-DiffArea;
if (DefArea==false){
DefArea=true;
mindiffarea=DiffArea;
for (int i=1;i<=N;++i)
Solution[i]=2;
for (int i=1;i<=NPlanePoints;++i)
Solution[Points[PlanePoints[i]].nr]=1;
if (Solution[1]==2)
for (int i=1;i<=N;++i)
Solution[i]=3-Solution[i];
return ;
}
if (DiffArea<mindiffarea) {
mindiffarea=DiffArea;
for (int i=1;i<=N;++i)
Solution[i]=2;
for (int i=1;i<=NPlanePoints;++i)
Solution[Points[PlanePoints[i]].nr]=1;
if (Solution[1]==2)
for (int i=1;i<=N;++i)
Solution[i]=3-Solution[i];
return ;
}
if (DiffArea==mindiffarea){
for (int i=1;i<=N;++i)
PartSol[i]=2;
for (int i=1;i<=NPlanePoints;++i)
PartSol[Points[PlanePoints[i]].nr]=1;
if (PartSol[1]==2)
for (int i=1;i<=N;++i)
PartSol[i]=3-PartSol[i];
if (LessThan())
for (int i=1;i<=N;++i) Solution[i]=PartSol[i];
}
}
int main(){
freopen("gradina.in","r",stdin);
freopen("gradina.out","w",stdout);
scanf("%d",&N);
for (int i=1;i<=N;++i){
scanf("%d%d",&Points[i].x,&Points[i].y);
Points[i].nr=i;
}
sort(Points+1,Points+N+1,cmp);
fclose(stdin);
DefArea=false;
for (int i=1;i<=N;++i)
for (int j=1;j<=N;++j)
if (i!=j) Split(i,j);
printf("%lld",mindiffarea/2);
if (mindiffarea%2) printf(".5"); else printf(".0");
printf("\n");
for (int i=1;i<=N;++i)
if (Solution[i]==1) printf("I"); else printf("V");
printf("\n");
fclose(stdout);
return 0;
}