Pagini recente » Cod sursa (job #2005550) | Cod sursa (job #277680) | Cod sursa (job #1010383) | Cod sursa (job #122679) | Cod sursa (job #1756469)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#define EPS 1e-6
#define MAXN 800
struct mycreation{
double x, y;
}a[MAXN+1];
double t[MAXN+1], k;
std::vector<int>v[MAXN];
const double alfa=0.73;
inline double arie(int p, mycreation e){
int q=p+1;
if(a[p].x>a[q].x){
int aux=p;
p=q;
q=aux;
}
return a[p].x*a[q].y-a[q].x*a[p].y+a[q].x*e.y-e.x*a[q].y+e.x*a[p].y-a[p].x*e.y;
}
inline double intersection(mycreation p, mycreation q){
return p.y+(q.y-p.y)*(k-p.x)/(q.x-p.x);
}
bool cmp(const int p, const int q){
return intersection(a[p], a[p+1])<intersection(a[q], a[q+1]);
}
inline mycreation rotim(mycreation a){
double x=a.x, y=a.y;
a.x=x*cos(alfa)-y*sin(alfa);
a.y=x*sin(alfa)+y*cos(alfa);
return a;
}
int main(){
int ans, n, m, rez, poz;
mycreation q;
FILE *fin, *fout;
fin=fopen("poligon.in", "r");
fout=fopen("poligon.out", "w");
fscanf(fin, "%d%d", &n, &m);
for(int i=0; i<n; i++){
fscanf(fin, "%lf%lf", &a[i].x, &a[i].y);
a[i]=rotim(a[i]);
t[i]=a[i].x;
}
a[n]=a[0];
std::sort(t, t+n);
t[n]=t[n-1]+2;
for(int i=1; i<n; i++){
for(int j=0; j<n; j++)
if(((a[j].x<t[i-1]+EPS)&&(t[i]<a[j+1].x+EPS))||((a[j+1].x<t[i-1]+EPS)&&(t[i]<a[j].x+EPS)))
v[i].push_back(j);
k=0.5*(t[i]+t[i+1]);
std::sort(v[i].begin(), v[i].end(), cmp);
}
ans=0;
for(int i=0; i<m; i++){
fscanf(fin, "%lf%lf", &q.x, &q.y);
q=rotim(q);
if((t[0]<q.x+EPS)&&(q.x<t[n-1]+EPS)){
if((t[0]>q.x-EPS)|(q.x+EPS>t[n-1])) ans++;
else{
rez=0;
for(int pas=1<<9; pas; pas>>=1)
if((rez+pas<n)&&(t[rez+pas]<=q.x))
rez+=pas;
rez++;
if((q.x-t[rez]>-EPS)&&(q.x-t[rez]<EPS)) ans++;
else{
poz=-1;
for(int pas=1<<9; pas; pas>>=1)
if((poz+pas<(int)v[rez].size())&&(arie(v[rez][poz+pas], q)>-EPS))
poz+=pas;
if(poz>=0){
if(arie(v[rez][poz], q)<EPS) ans++;
else ans+=(poz+1)%2;
}
}
}
}
}
fprintf(fout, "%d\n", ans);
fclose(fin);
fclose(fout);
return 0;
}