Cod sursa(job #415407)

Utilizator freak93Adrian Budau freak93 Data 11 martie 2010 11:52:46
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

const char iname[]="poligon.in";
const char oname[]="poligon.out";
const int maxn=1605;

ifstream f(iname);
ofstream g(oname);

typedef pair<int,int> point;
typedef pair<point,point> line;

point a[maxn],b[maxn];
pair<vector<line>,int> E[maxn];
vector<line> aux;

int i,j,n,m,first,second,step,band,rez,weird;

long long area(point a,point b,point c)
{
    long long areax=1LL*a.first*(b.second-c.second)+1LL*b.first*(c.second-a.second)+1LL*c.first*(a.second-b.second);
    return areax;
}

bool fcomp(const line& a,const line& b)
{
    if(a.first<a.second)
        return (area(a.first,a.second,b.second)>=0);
    return (area(a.second,a.first,b.second)>=0);
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
        f>>a[i].first>>a[i].second,a[i].first*=2,a[i].second*=2,b[i]=a[i];
    sort(b+1,b+n+1);
    for(i=1;i<=n;++i)
        E[i].second=b[i].first;
    E[0].second=-1;
    E[n+1].second=70000;
    a[0]=a[n];
    /*for(i=0;i<n;++i)
        for(j=1;j<=n;++j)
            if(a[i].first!=a[i+1].first)
                if((a[i].first<=E[j].second&&a[i+1].first>=E[j+1].second)||(a[i+1].first<=E[j].second&&a[i].first>=E[j+1].second))
                    E[j].first.push_back(make_pair(a[i],a[i+1]));*/
    for(i=0;i<=n;++i)
        E[i].first.push_back(make_pair(make_pair(-1,-1),make_pair(70000,-1)));

    for(i=1;i<=n;++i)
        sort(E[i].first.begin(),E[i].first.end(),fcomp);
    for(i=0;i<=n;++i)
    {
        g<<"Banda:"<<i<<"\n";
        for(vector<line>::iterator it=E[i].first.begin();it!=E[i].first.end();++it)
            g<<it->first.first<<" "<<it->first.second<<" "<<it->second.first<<" "<<it->second.second<<"\n";
        g<<"\n";
    }

   /* for(i=1;i<=m;++i)
    {
        f>>first>>second;
        first*=2;
        second*=2;
        for(step=1;step<n;step<<=1);
        for(j=0;step;step>>=1)
            if(j+step<=n&&E[j+step].second<=first)
                j+=step;
        band=j;
        if(band==n&&first==E[band].second)
            --band;
        for(step=1;step<E[band].first.size();step<<=1);
        weird=E[band].first.size();
        for(j=0;step;step>>=1)
            if(j+step<E[band].first.size()&&fcomp(E[band].first[j+step],make_pair(make_pair(first,second),make_pair(first,second))))
                j+=step;
        if((j&1)==0)
            if(j<weird&&area(min(E[band].first[j].first,E[band].first[j].second),max(E[band].first[j].first,E[band].first[j].second),make_pair(first,second))==0)
                ++rez;
            else;
        else
            ++rez;
    }*/

    g<<rez<<"\n";

    f.close();
    g.close();

    return 0;
}