frp

Untitled

frp
May 5th, 2011
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.00 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <map>
  4. #include <cmath>
  5. #include <algorithm>
  6. using namespace std;
  7. double S(double x1,double y1,double x2,double y2,double x3,double y3)
  8. {
  9.     return abs((x1*(y2-y3)-x2*(y1-y3)+x3*(y1-y2))/2);
  10. }
  11. bool check(double x1,double y1,double x2,double y2,double x3,double y3,double x,double y)
  12. {
  13.     return S(x1,y1,x2,y2,x,y)+S(x1,y1,x3,y3,x,y)
  14.         +S(x2,y2,x3,y3,x,y)==S(x1,y1,x2,y2,x3,y3);
  15. }
  16. double to2p(double x)
  17. {
  18.     return x>=0?x:x+2*M_PI;
  19. }
  20. int main()
  21. {
  22.     ifstream in("theodore.in");
  23.     ofstream out("theodore.out");
  24.     int n,m,k;
  25.     in>>n>>m>>k;
  26.     int li=0;
  27.     vector<int> x(n+1),y(n+1);
  28.     for(int i=0;i<n;i++)
  29.     {
  30.         in>>x[i]>>y[i];
  31.     }
  32.     li=n;x[n]=(x[0]+x[2])/2;y[n]=(y[0]+y[2])/2;
  33.     vector<pair<double,int> > p_ang;
  34.     for(int i=0;i<n;i++)
  35.         p_ang.push_back(make_pair(to2p(atan2(y[i]-y[li],x[i]-x[li])),i));
  36.     sort(p_ang.begin(),p_ang.end());
  37.     int cnt=0;
  38.     for(int i=0;i<m;i++)
  39.     {
  40.         int xp,yp;
  41.         in>>xp>>yp;
  42.         double pa=to2p(atan2(yp-y[li],xp-x[li]));
  43.         if(xp==x[li] && yp==y[li])cnt++;
  44.         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++;
  45.         else
  46.             if(pa>=p_ang[0].first && pa<=p_ang.back().first)
  47.             {
  48.                 int l=0,r=p_ang.size()-1;
  49.                 while(1)
  50.                 {
  51.                     if(l==r)
  52.                     {
  53.                         bool res=false;
  54.                         if(l!=p_ang.size()-1)
  55.                             res|=check(x[p_ang[l].second],y[p_ang[l].second],
  56.                                        x[li],y[li],x[p_ang[l+1].second],
  57.                                        y[p_ang[l+1].second],xp,yp);
  58.                         if(l>0)
  59.                             res|=check(x[p_ang[l].second],y[p_ang[l].second],
  60.                                        x[li],y[li],x[p_ang[l-1].second],
  61.                                        y[p_ang[l-1].second],xp,yp);
  62.                         cnt+=res;
  63.                         break;
  64.                     }
  65.                     else if(r-l==1)
  66.                     {
  67.                         int l_i=p_ang[l].second,r_i=p_ang[r].second;
  68.                         cnt+=check(x[li],y[li],x[l_i],y[l_i],x[r_i],y[r_i],xp,yp);
  69.                         break;
  70.                     }
  71.                     int m=(r+l)/2;
  72.                     if(pa<=p_ang[m].first)r=m;
  73.                     else l=m;
  74.                 }
  75.             }
  76.     }
  77.     out<<(cnt>=k?"YES\n":"NO\n");
  78.     in.close();
  79.     out.close();
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment