Pagini recente » Cod sursa (job #23545) | Cod sursa (job #2223259) | Cod sursa (job #844503) | Cod sursa (job #1982642) | Cod sursa (job #1404714)
#include <fstream>
#include <cstdlib>
#include <algorithm>
using namespace std;
ifstream f("overlap.in");
ofstream g("overlap.out");
int N;
struct Element{
int first,second,poz;
} Point[805];
pair <int,int> Rotate[805];
int Link[805],Result[805],Use[805];
int Area[805];
void Read()
{
f>>N;
for(int i=1;i<=N;i++)
f>>Point[i].first>>Point[i].second,Rotate[i].first=Point[i].first,Rotate[i].second=Point[i].second,Point[i].poz=i;;
}
void rotate()
{
int i;
for(int i=1;i<=N;i++)
{
int x=-Rotate[i].second,y=Rotate[i].first;
Rotate[i]=make_pair(x,y);
}
}
inline bool compare(Element a,Element b)
{
if(a.first==b.first)
return a.second<b.second;
return a.first<b.first;
}
int binSearch(pair <int,int> val)
{
int left=1,right=N,mid,sol=0;
while(left<=right)
{
mid=(left+right)/2;
if(val>make_pair(Point[mid].first,Point[mid].second))
left=mid+1;
if(val<make_pair(Point[mid].first,Point[mid].second))
right=mid-1;
if(val==make_pair(Point[mid].first,Point[mid].second))
return mid;
}
return 0;
}
void Pair()
{
for(int i=1;i<=N;i++)
Use[i]=0;
for(int i=N;i>=1;i--)
{
if(Use[Point[i].poz]==0)
{
int number=0;
++number;
int j;
Use[Point[i].poz]=1;
j=Link[Point[i].poz];
while(j!=-1 && Use[j]==0)
{
++number;
Use[j]=1;
j=Link[j];
}
if(number%2==1)
return;
}
}
for(int i=1;i<=N;i++)
Use[i]=0;
for(int i=N;i>=1;i--)
{
if(Use[Point[i].poz]==0)
{
int number=0;
int j;
Result[Point[i].poz]=number%2+1;
Use[Point[i].poz]=1;
j=Link[Point[i].poz];
while(j!=-1 && Use[j]==0)
{
++number;
Use[j]=1;
Result[j]=number%2+1;
j=Link[j];
}
}
}
for(int i=1;i<=N;i++)
g<<Result[i]<<"\n";
exit(0);
}
void Browse()
{
for(int i=2;i<=N;i++)
{
int shiftX,shiftY;
shiftX=Point[1].first-Rotate[i].first;
shiftY=Point[1].second-Rotate[i].second;
for(int j=1;j<=N;j++)
{
int newX=Rotate[j].first+shiftX,newY=Rotate[j].second+shiftY;
int p=binSearch(make_pair(newX,newY));
if(p==0)
Link[Point[j].poz]=-1;
else
Link[Point[j].poz]=Point[p].poz;
}
Pair();
}
}
int main()
{
Read();
sort(Point+1,Point+N+1,compare);
for(int i=1;i<=N;i++)
Rotate[i].first=Point[i].first,Rotate[i].second=Point[i].second;
for(int i=0;i<4;i++)
{
Browse();
rotate();
}
return 0;
}