Pagini recente » Cod sursa (job #2118375) | Cod sursa (job #606137) | Cod sursa (job #1428096) | Cod sursa (job #1007845) | Cod sursa (job #980432)
Cod sursa(job #980432)
#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;}