Pagini recente » Cod sursa (job #127115) | Cod sursa (job #2106164) | Cod sursa (job #291672) | Cod sursa (job #81109) | Cod sursa (job #2404809)
#include <iostream>
#include <fstream>
using namespace std;
int v[800][2];
double verifyCrossing(int i,int a,int &dir_crossed,int n){
double y;
int j=(i+1)%n;
dir_crossed=-1;
if(v[i][0]==v[j][0])
return -1;
y=((double)a-(double)v[i][0])*((double)v[j][1]-(double)v[i][1])/((double)v[j][0]-(double)v[i][0])+(double)v[i][1];
if((y==v[i][1] && v[i][0]<v[j][0]) || (y==v[j][1] && v[j][0]<v[i][0])){
dir_crossed=1;
return y;
}
else if((y==v[i][1] && v[i][0]>v[j][0]) || (y==v[j][1] && v[j][0]>v[i][0])){
dir_crossed=2;
return y;
}
else if((y>v[i][1] && y<v[j][1] && v[i][1]<v[j][1]) || (y>v[j][1] && y<v[i][1] && v[j][1]<v[i][1])){
return y;
}
else{
return -1;
}
}
int seeIfInside(int a,int b,int n){
int dir_trecut=-1,dir_first;
int dir_crossed;
int bigger=0,smaller=0;
double y;
double first,trecut=-1;
int i;
for(i=0;i<n;i++){
y=verifyCrossing(i,a,dir_crossed,n);
if(i==0){
first=y;
dir_first=dir_crossed;
}
if(y!=-1 && (dir_crossed==-1 || (dir_crossed!=-1 && trecut!=y))){
if(y==b)
return 1;
else if(y>b)
bigger++;
else
smaller++;
}
else if(y!=-1 && dir_crossed!=-1 && trecut==y && dir_crossed==dir_trecut){
if(y==b)
return 1;
else if(y>b)
bigger--;
else
smaller--;
}
dir_trecut=dir_crossed;
trecut=y;
}
trecut=first;
dir_crossed=dir_first;
if(y!=-1 && dir_crossed!=-1 && trecut==y && dir_crossed==dir_trecut){
if(y==b)
return 1;
else if(y>b)
bigger-=2;
else
smaller-=2;
}
if(bigger%2==1) return 1;
else return 0;
}
int main()
{
ifstream fin("poligon.in");
ofstream fout("poligon.out");
int n,m;
fin>>n>>m;
int i;
for(i=0;i<n;i++)
fin>>v[i][0]>>v[i][1];
int a,b;
int nr=0;
for(i=0;i<m;i++){
fin>>a>>b;
nr+=seeIfInside(a,b,n);
}
fout<<nr<<"\n";
return 0;
}