Mai intai trebuie sa te autentifici.
Cod sursa(job #425439)
Utilizator | Data | 25 martie 2010 18:57:02 | |
---|---|---|---|
Problema | Poligon | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.77 kb |
# include <fstream>
# include <iostream>
# include <vector>
# include <algorithm>
# define EPS 0.001
using namespace std;
struct pct{
double y, x;
pct(){}
pct(double I, double J){
x=I;y=J;}
};
vector<pct> P, V;
int n, m, rez;
void read()
{
ifstream fin ("poligon.in");
fin>>n>>m;
int x, y;
for (int i=1;i<=n;i++)
{
fin>>x>>y;
P.push_back(pct(x, y));
}
for(int i=1;i<=m;i++)
{
fin>>x>>y;
V.push_back(pct(x, y));
}
}
int in_p (pct p)
{
double x;
int ni=0;
pct A;
vector<pct>::iterator I;
// cout<<p.x<<" "<<p.y;
for (I=P.begin();I+1<P.end();++I)
{
if ((p.y>=I->y && p.y<=(I+1)->y) || (p.y<=I->y && p.y>=(I+1)->y))
{
if (I->x==(I+1)->x)
{
if (I->x>=p.x)
++ni;
}
else
if (I->y== (I+1)->y)
{
if (I->y==p.y && p.x>=I->x && p.x>=(I+1)->x)
++ni;
}
else
{
// cout<<p.x<<" "<<p.y<<" cu "<<I->x<<" "<<I->y<<", "<<(I+1)->x<<" "<<(I+1)->y<<" = ";
x=(p.y-I->y)*((I+1)->x-I->x)/((I+1)->y-I->y)+I->x;
// cout<<x<<" "<<p.y<<endl;
if (x>=p.x)
++ni;
}
}
}
A=*(P.begin());
// cout<<"capatu "<<I->x<<" "<<I->y<<endl;
if ((p.y>=I->y && p.y<=A.y) || (p.y<=I->y && p.y>=A.y))
{
if (I->x==A.x)
{
if (I->x>=p.x)
++ni;
}
else
if (I->y==A.y)
{
if (I->y==p.y && p.x>=I->x && p.x>=A.x)
++ni;
}
else
{
// cout<<p.x<<" "<<p.y<<" cu "<<I->x<<" "<<I->y<<", "<<(I+1)->x<<" "<<(I+1)->y<<" = ";
x=(p.y-I->y)*(A.x-I->x)/(A.y-I->y)+I->x;
// cout<<x<<" "<<p.y<<endl;
if (x>=p.x)
++ni;
}
}
return ni%2;
}
void solve ()
{
for(vector<pct>::iterator I=V.begin();I<V.end();++I)
if (in_p(*I))
++rez;
}
void afis ()
{
ofstream fout ("poligon.out");
fout<<rez<<"\n";
}
int main ()
{
read ();
solve ();
afis ();
return 0;
}