Cod sursa(job #1408300)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 29 martie 2015 22:57:33
Problema Overlap Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
#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 Next[805],Result[805],Use[805],Prev[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=Point[i].poz;
            while(Prev[j]!=-1 && Prev[j]!=Point[i].poz)
                j=Prev[j];
            Use[j]=1;
            j=Next[j];
            while(j!=-1 && Use[j]==0)
            {
                ++number;
                Use[j]=1;
                j=Next[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;
            ++number;
            int j=Point[i].poz;
            while(Prev[j]!=-1 && Prev[j]!=Point[i].poz)
                j=Prev[j];
            Use[j]=1;
            Result[j]=number%2+1;
            j=Next[j];

            while(j!=-1 && Use[j]==0)
            {
                ++number;
                Use[j]=1;
                Result[j]=number%2+1;
                j=Next[j];
            }
        }
    }
    for(int i=1;i<=N;i++)
        g<<Result[i]<<"\n";
    exit(0);
}
void Browse()
{

    for(int i=2;i<=N;i++)
    {
        for(int i=1;i<=N;i++)
            Next[i]=Prev[i]=-1;
        int shiftX,shiftY;
        shiftX=Rotate[i].first-Point[1].first;
        shiftY=Rotate[i].second-Point[1].second;
        for(int j=1;j<=N;j++)
        {
            int newX=Point[j].first+shiftX,newY=Point[j].second+shiftY;
            int p=binSearch(make_pair(newX,newY));
            if(p==0 || j==p)
                Next[Point[j].poz]=-1,Prev[Point[j].poz]=-1;
            else
                Next[Point[j].poz]=Point[p].poz,Prev[Point[p].poz]=Point[j].poz;
        }
        Pair();
        for(int i=1;i<=N;i++)
            Next[i]=Prev[i]=-1;
    }

}
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;
}