Pagini recente » Cod sursa (job #2869251) | Cod sursa (job #1055003) | Cod sursa (job #2741793) | Cod sursa (job #1235671) | Cod sursa (job #3223828)
#include <fstream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
vector < pair < int , int > > original,points;
vector < int > conectat,tip;
ifstream cin("overlap.in");
ofstream cout("overlap.out");
int n;
void schimbare90(pair < int , int >& a)
{
swap(a.first,a.second);
a.first*=(-1);
}
bool solve(pair < int , int > dif)
{
for(int i=1;i<=n;i++){
conectat[i]=-1;
tip[i]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
continue;
if(make_pair(original[j].first-points[i].first,original[j].second-points[i].second) == dif)
conectat[i]=j;
}
}
queue < int > q;
for(int i=1;i<=n;i++){
if(conectat[i]==-1)
q.push(i);
}
while(!q.empty())
{
bool ok=0;
if(tip[q.front()])
{
q.pop();
continue;
}
for(int i=1;i<=n;i++)
{
if(tip[i]==0 && conectat[i]==q.front())
{
tip[q.front()]=1;
tip[i]=2;
conectat[i]=-1;
ok=1;
break;
}
}
if(ok==0)
return 0;
for(int i=1;i<=n;i++)
{
if(conectat[i]==-1)
q.push(i);
}
q.pop();
}
int cnt=0;
for(int i=1;i<=n;i++)
{
if(tip[i])
cnt++;
}
if(cnt==n)
{
for(int i=1;i<=n;i++)
cout<<tip[i]<<'\n';
return 1;
}
return 0;
}
int main()
{
cin>>n;
points.resize(n+1);
conectat.resize(n+1);
tip.resize(n+1);
for(int i=1;i<=n;i++)
cin>>points[i].first>>points[i].second;
original=points;
for(int k=0;k<4;k++)
{
for(int i=1;i<=1;i++)
{
for(int j=2;j<=n;j++)
{
if(i==j)
continue;
pair < int , int > temp = {original[j].first-points[i].first,original[j].second-points[i].second};
if(solve(temp))
return 0;
}
}
for(int i=1;i<=n;i++)
schimbare90(points[i]);
}
return 0;
}