Pagini recente » Cod sursa (job #1174119) | Cod sursa (job #1877131) | Cod sursa (job #26545) | Cod sursa (job #3201366) | Cod sursa (job #1156730)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
#define per pair<long double,long double>
#define mp make_pair
#define x first
#define y second
#define DN 805
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
struct st{
per a,b;
long double A,B,C;
long double mij;
};
int n,m,rez;
per pol[DN],pol_initial[DN],bucket[DN];
vector < st > banda[DN];
void read(){
f>>n>>m;
for(int i=1;i<=n;++i){
f>>pol[i].x>>pol[i].y;
pol_initial[i] = pol[i];
}
}
bool se_intersect(per a,per b,per c,per d){
if(a.x > d.x)
swap(a,d);
if(a.x <= b.x && c.x <= d.x)
return true;
return false;
}
bool cmp(st a,st b){
return a.mij < b.mij;
}
void prec(){ /// precalculare
for(int i=1;i<n;++i){ /// pentru fiecare banda
//int i = 2;
/// banda e determinata de : [pol[i].x , pol[i+1].x]
bucket[i] = mp( pol[i].x , pol[i+1].x );
//cout<<"Banda :"<<i<<" "<<i+1<<" ST:"<<pol[i].x<<" DR :"<<pol[i+1].x<<endl;
for(int j=1 ; j<=n ; ++j){
int next_j = j + 1;
if(next_j > n)
next_j-=n;
if(se_intersect(pol_initial[j],pol[i],pol[i+1],pol_initial[ next_j ])){
//cout<<j<<" "<<next_j<<endl;
//cout<<"x_st :"<<pol_initial[j].x<<" x_dr :"<<pol_initial[next_j].x<<endl;
st p;
p.a = pol_initial[j];
p.b = pol_initial[next_j];
if(p.a.x > p.b.x)
swap(p.a,p.b);
/// ecuatia dreptei
p.A = (p.b.y - p.a.y);
p.B = -(p.b.x - p.a.x);
p.C = -p.a.x*(p.b.y - p.a.y) + p.a.y*( p.b.x - p.a.x);
/// intersectia cu banda devine
p.a.x = bucket[i].x;
p.a.y = -( p.A * p.a.x + p.C) / p.B;
p.b.x = bucket[i].y;
p.b.y = -( p.A * p.b.x + p.C) / p.B;
p.mij = (p.a.y + p.b.y) * 0.5;
banda[i].push_back(p);
}
}
sort(banda[i].begin(),banda[i].end(),cmp);
}
}
bool is_inside(per p,int ind){
return (bucket[ind].x <= p.x && p.x <= bucket[ind].y);
}
bool is_less(per p,int ind){
return ( p.x < bucket[ind].x );
}
int find_bucket( per p ){
int st = 1 , dr = n - 1 ;
while( st<=dr ){
int mij = (st+dr)>>1;
if(is_inside(p,mij))
return mij;
if(is_less(p,mij))
dr = mij - 1;
else
st = mij + 1;
}
return -1;
}
long double fct( per p, st line){
// if( y_dreapta == p.y )
// on_border = true;
long double tmp = line.A * p.x + line.B * p.y + line.C;
/*cout<<line.a.x<<" "<<line.a.y<<" | "<<line.b.x<<" "<<line.b.y<<endl;
cout<<"A : "<<line.A<<" B:"<<line.B<<" "<<line.C<<endl;
cout<< tmp <<endl;*/
return tmp ;
}
int find_under( per p, int ind){
int st = 1 , dr = banda[ind].size(), rez = 0;
while(st<=dr){
int mij = (st+dr)>>1;
if( fct(p,banda[ind][mij - 1]) < 0 ){
st = mij + 1;
rez = mij;
}
else
if( fct(p,banda[ind][mij - 1]) > 0)
dr = mij - 1;
else
return 1; /// e pe dreatpa
}
return rez;
}
void solve(){
sort(pol+1,pol+n+1);
prec();
for(int i=1;i<=m;++i){
per p;
f>>p.x>>p.y;
int bucket = find_bucket(p);
if( bucket == -1) continue; /// nu face parte din nicio banda
int under = find_under(p,bucket);
if(under%2 == 1)
++rez;
//cout<<"punctul :"<<i<<" in bucketul:"<<bucket<<" si are sub el: "<<under<<endl;
}
g<<rez;
}
int main()
{
read();
solve();
return 0;
}