Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <map>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- double S(double x1,double y1,double x2,double y2,double x3,double y3)
- {
- return abs((x1*(y2-y3)-x2*(y1-y3)+x3*(y1-y2))/2);
- }
- bool check(double x1,double y1,double x2,double y2,double x3,double y3,double x,double y)
- {
- return S(x1,y1,x2,y2,x,y)+S(x1,y1,x3,y3,x,y)
- +S(x2,y2,x3,y3,x,y)==S(x1,y1,x2,y2,x3,y3);
- }
- double to2p(double x)
- {
- return x>=0?x:x+2*M_PI;
- }
- int main()
- {
- ifstream in("theodore.in");
- ofstream out("theodore.out");
- int n,m,k;
- in>>n>>m>>k;
- int li=0;
- vector<int> x(n+1),y(n+1);
- for(int i=0;i<n;i++)
- {
- in>>x[i]>>y[i];
- }
- li=n;x[n]=(x[0]+x[2])/2;y[n]=(y[0]+y[2])/2;
- vector<pair<double,int> > p_ang;
- for(int i=0;i<n;i++)
- p_ang.push_back(make_pair(to2p(atan2(y[i]-y[li],x[i]-x[li])),i));
- sort(p_ang.begin(),p_ang.end());
- int cnt=0;
- for(int i=0;i<m;i++)
- {
- int xp,yp;
- in>>xp>>yp;
- double pa=to2p(atan2(yp-y[li],xp-x[li]));
- if(xp==x[li] && yp==y[li])cnt++;
- else if(check(x[p_ang[0].second],y[p_ang[0].second],x[p_ang.back().second],y[p_ang.back().second],x[li],y[li],xp,yp))cnt++;
- else
- if(pa>=p_ang[0].first && pa<=p_ang.back().first)
- {
- int l=0,r=p_ang.size()-1;
- while(1)
- {
- if(l==r)
- {
- bool res=false;
- if(l!=p_ang.size()-1)
- res|=check(x[p_ang[l].second],y[p_ang[l].second],
- x[li],y[li],x[p_ang[l+1].second],
- y[p_ang[l+1].second],xp,yp);
- if(l>0)
- res|=check(x[p_ang[l].second],y[p_ang[l].second],
- x[li],y[li],x[p_ang[l-1].second],
- y[p_ang[l-1].second],xp,yp);
- cnt+=res;
- break;
- }
- else if(r-l==1)
- {
- int l_i=p_ang[l].second,r_i=p_ang[r].second;
- cnt+=check(x[li],y[li],x[l_i],y[l_i],x[r_i],y[r_i],xp,yp);
- break;
- }
- int m=(r+l)/2;
- if(pa<=p_ang[m].first)r=m;
- else l=m;
- }
- }
- }
- out<<(cnt>=k?"YES\n":"NO\n");
- in.close();
- out.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment