I read the tutorial of contest 27 . But in that time i already coded a solution which is greedy i think. Here is what i do
1) I calculate for each segment, with how many segment it intersects.
2)Then for each segment 1 to m
--if it has min one intersection and if it doesn't intersect with others who are already been put outside and if it is not already been put outside , I color it to keep track of the segments put outside.And i also store this segment so that i can check it with the other segments who will be put outside in the future to check intersection.Then break and go to step 1.
And i do the above process until i find that i can not put anymore segments outside. And at last i check if there is any collision between the segments. If there then i output impossible else i output who are colored as outside and who are not colored as inside :)
But this code fails for test case 23 :(
Is my procedure is ok ?? Can anyone explain please. Here is my code
#include <sstream>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
#define inf 99999999
using namespace std;
typedef struct
{
int x,y,cnt;
}Ind;
Ind ar[110],arr [110];
int flg[110];
bool fl;
int i,j,ed,mn,mx,node,edge;
void find() // checking for every segment how many times intersected with other segments
{
int i,j;
fl = 0;
for(i=0;i<edge;i++)
{
ar[i].cnt=0;
if(!flg[i])
for(j=0;j<edge;j++)
{
if(i==j || flg[j])continue;
if(ar[i].x>=ar[j].x && ar[i].y<=ar[j].y)continue;
if(ar[i].x>=ar[j].y || ar[i].y<=ar[j].x)continue;
if(ar[i].x<=ar[j].x && ar[i].y>=ar[j].y)continue;
ar[i].cnt++;
fl = 1;
}
}
}
bool chek(int i) // checking if puting outside the current segment causes intersection with other segments which are already outside
{
int j;
for(j=0;j<ed;j++)
{
if(ar[i].x>=arr[j].x && ar[i].y<=arr[j].y)continue;
if(ar[i].x>=arr[j].y || ar[i].y<=arr[j].x)continue;
if(ar[i].x<=arr[j].x && ar[i].y>=arr[j].y)continue;
return 0;
}
return 1;
}
int main()
{
//freopen("out.txt","w",stdout);
while(cin>>node>>edge)
{
for(i=0;i<edge;i++)
{
cin>>ar[i].x>>ar[i].y;
mn = min (ar[i].x,ar[i].y);
mx = max (ar[i].x,ar[i].y);
ar[i].x = mn;
ar[i].y = mx;
}
ed=0;
do
{
find();
fl=0;
for(i=0;i<edge;i++)
{
if(ar[i].cnt && chek(i) && !flg[i])
{
arr[ed].x = ar[i].x;
arr[ed++].y = ar[i].y;
flg[i]=1;
fl=1;
break;
}
}
}while(fl);
find();
if(fl)
{
cout<<"Impossible";
return 0;
}
for(i=0;i<edge;i++)
{
//
if(flg[i])cout<<"o";
else cout<<"i";
}
}
return 0;
}
Comments (1)
0
+2 
