Cod sursa(job #980447)

Utilizator stefanzzzStefan Popa stefanzzz Data 4 august 2013 18:16:40
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.56 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,ad[MAXN],bd[MAXN],cd[MAXN];
set<int> benziaux;
set<int>::iterator it;
vector< pair<int,int> > puncte;
vector<int> benzi,v;
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 (ad[b]*x+bd[b]*y+cd[b]<=0);}

bool Comp3(int a,pair<int,int> b){
    return a<=b.first;}

bool Comp4(pair<int,int> a,pair<int,int> b){
    return a.first<b.first;}

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));
            v.push_back(puncte[i].first);}
        ad[i]=puncte[i].second-puncte[i+1].second;
        bd[i]=puncte[i].first-puncte[i+1].first;
        cd[i]=-(ad[i]*puncte[i].first+bd[i]*puncte[i].second);
        if(bd[i]<0){
            ad[i]*=(-1);
            bd[i]*=(-1);
            cd[i]*=(-1);}}
    for(i=0;i<v.size();i++)
        sort(verticale[v[i]].begin(),verticale[v[i]].end(),Comp4);
    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)
            aux=segmente_banda[bnd][nr-1];
        if((nr%2)||(nr&&(ABS(ad[aux]*x+bd[aux]*y+cd[aux])<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 a;
    a=upper_bound(verticale[x].begin(),verticale[x].end(),y,Comp3)-verticale[x].begin()-1;
    if(a>=0&&y>=verticale[x][a].first&&y<=verticale[x][a].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;}