Pagini recente » Cod sursa (job #2417215) | Cod sursa (job #720155) | Cod sursa (job #1896553) | Cod sursa (job #2533392) | Cod sursa (job #1201654)
#include <cstdio>
#include <algorithm>
#include <vector>
#define EPS 0.00001
using namespace std;
struct punct{
punct(){
x = y = 0;
}
double x,y;
bool operator <(punct P)
{
if(x < P.x) return 1;
if(x > P.x) return 0;
return y < P.y;
}
};
struct segment{
double a,b,c;/// ecuatia
punct A;
punct B;
};
int N,M;
vector<punct> v;
vector<segment> s;
punct centroid,pc;
segment fa_segment(punct A,punct B)
{
segment seg;
seg.A = A;
seg.B = B;
seg.a = A.y - B.y;
seg.b = B.x - A.x;
seg.c = A.x*(B.y-A.y) + A.y*(A.x-B.x);
return seg;
}
void read()
{
scanf("%d%d",&N,&M);
punct p;
for(int i = 1; i <= N; ++i){
scanf("%lf%lf",&p.x,&p.y);
v.push_back(p);
centroid.x += p.x;
centroid.y += p.y;
}
v.push_back(*v.begin());
for(int i = 1; i <= N; ++i)
s.push_back(fa_segment(v[i-1],v[i]));
centroid.x /= N;
centroid.y /= N;
centroid.x = -0.666013;
centroid.y += -0.666013;
}
int inters(segment S1,segment S2)
{
if( (S1.B.y - S1.A.y)*(S2.B.x - S2.A.x) ==
(S2.B.y - S2.A.y)*(S1.B.x - S1.A.x) )
return 0; /// au aceeasi panta deci sunt paralele si sper ca nu pot coincide ^_^
punct A,B,C,D;
A = S1.A;B = S1.B;
C = S2.A;D = S2.B;
double X,Y;
X = (S2.c*S1.b - S1.c*S2.b)/(S1.a*S2.b - S2.a*S1.b);
Y = (S2.c*S1.a - S1.c*S2.a)/(S1.b*S2.a - S2.b*S1.a);
if(A.x > B.x) swap(A.x,B.x);
if(A.y > B.y) swap(A.y,B.y);
if(C.x > D.x) swap(C.x,D.x);
if(C.y > D.y) swap(C.y,D.y);
if(A.x - EPS < X && X < B.x + EPS &&
C.x - EPS < X && X < D.x + EPS &&
A.y - EPS < Y && Y < B.y + EPS &&
C.y - EPS < Y && Y < D.y + EPS)
return 1;
return 0;
}
int det(punct A,punct B,punct C)
{
return A.x*B.y + B.x*C.y + A.y*C.x -
A.y*B.x - B.y*C.x - A.x*C.y;
}
void solve()
{
int ans = 0;
for(int i = 1; i <= M; ++i)
{
scanf("%lf%lf",&pc.x,&pc.y);
int nri = 0;
for(int i = 0; i < N; ++i)
{
if(inters(fa_segment(pc,centroid),s[i]) )
++nri;
if(det(pc,s[i].A,s[i].B) == 0)
{
nri = 0;
break;
}
}
if(nri % 2 == 0)
++ans;
}
printf("%d\n",ans);
}
int main()
{
freopen("poligon.in","r",stdin);
freopen("poligon.out","w",stdout);
read();
solve();
return 0;
}