Pagini recente » Cod sursa (job #657575) | Cod sursa (job #1057368) | Cod sursa (job #1145103) | Cod sursa (job #170081) | Cod sursa (job #2158474)
#include <iostream>
#include <fstream>
#include <algorithm>
#define inf 2147400000
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
int n,M,x,y,nrpuncte;
double m;
struct poligon{
int x,y;
double m;
}A[801];
bool cmp(poligon a, poligon b){
return a.m < b.m;
}
bool verif2(int x,int y,int mij){
long long val1,val2,val3;
val1=(A[mij].x*A[mij-1].y-A[mij].y*A[mij-1].x+A[mij-1].x*y-x*A[mij-1].y+x*A[mij].y-y*A[mij].x);
val2=(A[1].x*A[mij].y-A[1].y*A[mij].x+A[mij].x*y-x*A[mij].y+x*A[1].y-y*A[1].x);
val3=(A[mij-1].x*A[1].y-A[mij-1].y*A[1].x+A[1].x*y-x*A[1].y+x*A[mij-1].y-y*A[mij-1].x);
if(val1<=0 && val2<=0 && val3<=0)return 1;
if(val1>=0 && val2>=0 && val3>=0)return 1;
return 0;
}
bool verif(int x, int y){
int in,sf,mij;
in=2;
sf=n;
if(x!=A[1].x)m=double(y-A[1].y)/double(x-A[1].x);
else m=inf;
if(m>=A[2].m && m<=A[n].m){
while(in<=sf){
mij=(in+sf)/2;
if(m>=A[mij-1].m && m <= A[mij].m){
in=sf+1;
}
else
if(m<A[mij-1].m)sf=mij-1;
else in=mij+1;
}
if(verif2(x,y,mij))return 1;
}
return 0;
}
int main(){
f>>n>>M;\
for(int i=1; i<=n; ++i)
f>>A[i].x>>A[i].y;
A[1].m=-inf;
for(int i=2; i<=n; ++i)
if(A[i].x != A[1].x)A[i].m=(A[i].y-A[1].y)/(A[i].x-A[1].x);
else A[i].m=inf;
sort(A+1, A+n+1, cmp);
for(int i=1; i<=M; ++i){
f>>x>>y;
if(verif(x,y))++nrpuncte;
}
g<<nrpuncte<<'\n';
return 0;
}