Pagini recente » Cod sursa (job #2069989) | Cod sursa (job #3206009) | Cod sursa (job #3281572) | Cod sursa (job #1539716) | Cod sursa (job #1277341)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <ctime>
#define NMAX 805
#define eps 0.000001
using namespace std;
struct point{
double x,y;
point(double x=0,double y=0): x(x), y(y) {}
}v[NMAX];
double xs[NMAX];
double s,c;
inline void init_rand(){
srand(time(0));
double alpha=((rand()%10000+1)*0.0001)*M_PI;
//double alpha=0;
//double alpha=2.78125;
s=sin(alpha);
c=cos(alpha);
}
inline void trans(point &x){
double nx=x.x*c-x.y*s;
double ny=x.x*s+x.y*c;
x.x=nx;
x.y=ny;
}
struct segment{
point a,b;
double ym;
segment(point a=point(),point b=point()): a(a), b(b) {
ym=((a.y+b.y)*0.5);
}
};
inline double y_at_x(const segment &s,double x){
return ((x-s.a.x)*(s.b.y-s.a.y)/(s.b.x-s.a.x)+s.a.y);
}
bool operator<(const segment &a,const segment &b){
return a.ym<b.ym;
}
class fasie{
public:
double x0,x1;
vector<segment> segments;
fasie(): x0(0), x1(0) {}
bool inside(const point &x){
int st=0;
int dr=segments.size()-1;
int mijl=(dr>>1);
int rasp=-1;
double aux;
while(st<=dr){
aux=y_at_x(segments[mijl],x.x);
if(fabs(aux-x.y)<eps)
return 1;
else if(aux<x.y){
st=mijl+1;
rasp=mijl;
}
else
dr=mijl-1;
mijl=(st+dr)>>1;
}
return (!(rasp&1));
}
void add(const segment &s){
if(min(s.a.x,s.b.x)<=x0 && x1<=max(s.a.x,s.b.x))
segments.push_back(segment(point(x0,y_at_x(s,x0)),point(x1,y_at_x(s,x1))));
}
}fasii[NMAX];
int main()
{
ifstream cin("poligon.in");
ofstream cout("poligon.out");
int n=0,m=0,i,j;
cin>>n>>m;
init_rand();
for(i=1;i<=n;i++){
cin>>v[i].x>>v[i].y;
trans(v[i]);
xs[i]=v[i].x;
}
/*for(i=1;i<=n;i++){
cout<<"i="<<i<<' '<<v[i].x<<' '<<v[i].y<<endl;
}*/
sort(xs+1,xs+n+1);
for(i=1;i<n;i++){
fasii[i].x0=xs[i];
fasii[i].x1=xs[i+1];
for(j=1;j<n;j++)
fasii[i].add(segment(v[j],v[j+1]));
fasii[i].add(segment(v[1],v[n]));
sort(fasii[i].segments.begin(),fasii[i].segments.end());
}
/*cout<<"Fasiile sunt:"<<endl;
for(i=1;i<n;i++){
cout<<i<<' '<<fasii[i].x0<<' '<<fasii[i].x1<<endl;
cout<<"Cu continutul:"<<endl;
for(j=0;j<fasii[i].segments.size();j++)
cout<<j<<' '<<fasii[i].segments[j].a.x<<' '<<fasii[i].segments[j].a.y<<' '<<fasii[i].segments[j].b.x<<' '<<fasii[i].segments[j].b.y<<endl;
}*/
int ans=0;
point t;
int poz;
while(m--){
cin>>t.x>>t.y;
trans(t);
poz=lower_bound(xs+1,xs+n+1,t.x)-xs-1;
if(!poz)
continue;
ans+=fasii[poz].inside(t);
}
cout<<ans<<'\n';
cin.close();
cout.close();
return 0;
}