Cod sursa(job #980432)

Utilizator stefanzzzStefan Popa stefanzzz Data 4 august 2013 17:27:21
Problema Poligon Scor 70
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.89 kb
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
#define INF 100000
#define MAXN 820
#define EPS 0.0000001
#define MAXCOORD 60005
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");

char s[20];
int n,m,nrbenzi=-1,x,y,x1,x2,bnd,nr,cnt,aux,cnt2;
set<int> benziaux;
set<int>::iterator it;
vector< pair<int,int> > puncte;
vector<int> benzi;
vector<int> segmente_banda[MAXN];
vector< pair<int,int> > verticale[MAXCOORD];

double compute_y(int a,int x);

bool Comp2(int a,int b){
    return (compute_y(a,x1)+compute_y(a,x2))<(compute_y(b,x1)+compute_y(b,x2));}

bool Comp(int a,int b){
    return a<compute_y(b,x);}

double ABS(double a){
    return (a>0)?(a):(-a);}

bool e_pe_verticala();
int get_nr();

int main()
{
    int i;
    f>>n>>m;
    f.getline(s,20,'\n');
    benziaux.insert(INF);
    benziaux.insert(-INF);
    puncte.push_back(make_pair(0,0));
    for(i=1;i<=n;i++){
        f.getline(s,20,'\n');
        cnt2=0;
        x=get_nr();
        cnt2++;
        y=get_nr();
        puncte.push_back(make_pair(x,y));
        benziaux.insert(x);}
    for(i=1;i<=n;i++)
        if(puncte[i+1].first==puncte[i].first){
            x=puncte[i].second;
            y=puncte[i+1].second;
            if(x>y){
                aux=x;
                x=y;
                y=aux;}
            verticale[puncte[i].first].push_back(make_pair(x,y));}
    puncte.push_back(puncte[1]);
    for(it=benziaux.begin();*it<INF;it++){
        benzi.push_back(*it);
        ++nrbenzi;
        x1=*it;
        x2=*(++it);
        it--;
        for(i=1;i<=n;i++){
            if((puncte[i].first<=x1&&puncte[i+1].first>=x2)||(puncte[i].first>=x2&&puncte[i+1].first<=x1))
                segmente_banda[nrbenzi].push_back(i);}
        sort(segmente_banda[nrbenzi].begin(),segmente_banda[nrbenzi].end(),Comp2);}
    benzi.push_back(*it);
    for(i=1;i<=m;i++){
        f.getline(s,20,'\n');
        cnt2=0;
        x=get_nr();
        cnt2++;
        y=get_nr();
        bnd=upper_bound(benzi.begin(),benzi.end(),x)-benzi.begin()-1;
        nr=upper_bound(segmente_banda[bnd].begin(),segmente_banda[bnd].end(),y,Comp)-segmente_banda[bnd].begin();
        if((nr%2)||(nr&&(ABS(compute_y(segmente_banda[bnd][nr-1],x)-y))<EPS)||(e_pe_verticala()))
            cnt++;}
    g<<cnt<<'\n';
    f.close();
    g.close();
    return 0;
}

double compute_y(int a,int x){
    return ((double)(puncte[a+1].first*puncte[a].second-puncte[a].first*puncte[a+1].second-x*(puncte[a].second-puncte[a+1].second)))/(puncte[a+1].first-puncte[a].first);}

bool e_pe_verticala(){
    int i;
    for(i=0;i<verticale[x].size();i++)
        if(y>=verticale[x][i].first&&y<=verticale[x][i].second)
            return 1;
    return 0;}

int get_nr(){
    int a=s[cnt2++]-'0';
    while(s[cnt2]>='0'&&s[cnt2]<='9')
        a=a*10+s[cnt2++]-'0';
    return a;}