Advertisement
flash_7

ASC F

Mar 1st, 2017
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.22 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define nl puts ("")
  6. #define sp printf ( " " )
  7. #define phl printf ( "hello\n" )
  8. #define ff first
  9. #define ss second
  10. #define POPCOUNT __builtin_popcountll
  11. #define RIGHTMOST __builtin_ctzll
  12. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  13. #define MP make_pair
  14. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  15. #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
  16. #define CLR(x,y) memset(x,y,sizeof(x))
  17. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  18. #define MIN(a,b) ((a)<(b)?(a):(b))
  19. #define MAX(a,b) ((a)>(b)?(a):(b))
  20. #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
  21. #define SQ(x) ((x)*(x))
  22. #define ABS(x) ((x)<0?-(x):(x))
  23. #define FABS(x) ((x)+eps<0?-(x):(x))
  24. #define ALL(x) (x).begin(),(x).end()
  25. #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
  26. #define SZ(x) ((vlong)(x).size())
  27. #define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
  28. #define MOD(x,y) (((x)*(y))%mod)
  29. #define ODD(x) (((x)&1)==0?(0):(1))
  30. #define Set(N,cur) N=(N|(1<<cur))
  31. #define Reset(N,cur) N=(N&(~(1<<cur)))
  32. #define Check(N,cur) (!((N&(1<<cur))==0))
  33. #define dbgA(A,i) debug("At pos: ",i," = ",A[i])
  34. #define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
  35.  
  36. #ifdef forthright48
  37.      #include <ctime>
  38.      clock_t tStart = clock();
  39.      #define debug(args...) {dbg,args; cerr<<endl;}
  40.      #define timeStamp debug ("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
  41.      #define bug printf("%d\n",__LINE__);
  42.  
  43. #else
  44.      #define debug(args...)  // Just strip off all debug tokens
  45.      #define timeStamp
  46. #endif
  47.  
  48. struct debugger{
  49.     template<typename T> debugger& operator , (const T& v){
  50.         cerr<<v<<" ";
  51.         return *this;
  52.     }
  53. }dbg;
  54.  
  55. #define LL long long
  56. #define LLU long long unsigned int
  57. typedef long long vlong;
  58. typedef unsigned long long uvlong;
  59. typedef pair < int, int > pii;
  60. typedef pair < vlong, vlong > pll;
  61.  
  62. inline vlong gcd ( vlong a, vlong b ) {
  63.     a = ABS ( a ); b = ABS ( b );
  64.     while ( b ) { a = a % b; swap ( a, b ); } return a;
  65. }
  66.  
  67. vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
  68.     vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
  69.     x2 = 1; y2 = 0; x1 = 0; y1 = 1;
  70.     for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
  71.         q = r2 / r1; r = r2 % r1;
  72.         x = x2 - (q * x1); y = y2 - (q * y1);
  73.     }
  74.     *X = x2; *Y = y2;
  75.     return r2;
  76. }
  77.  
  78. inline vlong modInv ( vlong a, vlong m ) {
  79.     vlong x, y;
  80.     ext_gcd( a, m, &x, &y );
  81.     x %= m;
  82.     if ( x < 0 ) x += m;
  83.     return x;
  84. }
  85.  
  86. inline vlong power ( vlong a, vlong p ) {
  87.     vlong res = 1, x = a;
  88.     while ( p ) {
  89.         if ( p & 1 ) res = ( res * x );
  90.         x = ( x * x ); p >>= 1;
  91.     }
  92.     return res;
  93. }
  94.  
  95. inline vlong bigmod ( vlong a, vlong p, vlong m ) {
  96.     vlong res = 1 % m, x = a % m;
  97.     while ( p ) {
  98.         if ( p & 1 ) res = ( res * x ) % m;
  99.         x = ( x * x ) % m; p >>= 1;
  100.     }
  101.     return res;
  102. }
  103.  
  104. inline int STRLEN(char *s){
  105.     int p = 0; while(s[p]) p++; return p;
  106. }
  107.  
  108. inline LL SQRT(LL a){
  109.     LL v = sqrt(a);
  110.     if(SQ(v) == a) return v;
  111.     else if(SQ(v+1) == a) return v+1;
  112.     else if(SQ(v+2) == a) return v+2;
  113.     else return -1; /// a can no be written as p^2
  114. }
  115.  
  116. //int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
  117. //int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
  118. //int dir8[8][2] = {{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{1,1},{1,-1},{-1,1}};
  119.  
  120. const LL inf = 10000000000000000LL;
  121. const double pi = 2 * acos ( 0.0 );
  122. const double eps = 1e-8;
  123.  
  124. ///=========================  TEMPLATE ENDS HERE  ========================///
  125. ///=======================================================================///
  126.  
  127. #define Size 355
  128.  
  129. struct Point {
  130.     double x, y, r;
  131. };
  132.  
  133. vector<Point> List;
  134. double DP[Size];
  135. int vis[Size];
  136. vector<int> Graph[Size];
  137.  
  138. /// Compute A dot B:
  139. double dot(Point A, Point B){
  140.     return (A.x * B.x + A.y * B.y);
  141. }
  142.  
  143. ///Compute AB dot AC
  144. double dotProduct(Point A, Point B, Point C) {
  145.     Point AB = {B.x - A.x, B.y - A.y}; /// AB vector
  146.     Point AC = {C.x - A.x, C.y - A.y}; /// AC vector
  147.     return dot(AB, AC);
  148. }
  149.  
  150. double dist(Point A, Point B) {
  151.     return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
  152. }
  153.  
  154. /// Angel between vector (A-B) and (A-C)
  155. double getAngel(Point A, Point B, Point C){
  156.     double dotVal = dotProduct(A, B, C);
  157.     double a = dotVal/(dist(A,B) * dist(A,C));
  158.     if(a < -1.0) a = -1.0;
  159.     if(a > 1.0) a = 1.0;
  160.     return acos(a);
  161. }
  162.  
  163. bool DFS(int cur, Point P){
  164.     vis[cur] = 1;
  165.     for(int i = 0;i<Graph[cur].size();i++){
  166.         int v = Graph[cur][i];
  167.         double a = DP[cur] + getAngel(P, List[v], List[cur]);
  168.         if(vis[v] == -1){
  169.             DP[v] = a;
  170.             bool ret = DFS(v, P);
  171.             if(ret == true) return true;
  172.         }else{
  173.             double dif = a - DP[v];
  174.             if(FABS(dif-2.0*pi)<=eps || FABS(dif+2.0*pi)<=eps) return true;
  175.             //if(dif >= 2.0*pi || dif <= -2.0*pi) return true;
  176.         }
  177.     }
  178.     return false;
  179. }
  180.  
  181. void buildGraph(){
  182.     for(int i = 0;i<List.size();i++){
  183.         for(int j = i+1;j<List.size();j++){
  184.             double d = dist(List[i],List[j]);
  185.             double r = List[i].r + List[j].r;
  186.             if(r>d){
  187.                 Graph[i].pb(j);
  188.                 Graph[j].pb(i);
  189.                 //debug(i,j," = (", List[i].x,List[i].y," - ",List[j].x,List[j].y,")");
  190.             }
  191.         }
  192.     }
  193. }
  194.  
  195. bool solve(Point P){
  196.     for(int i = 0;i<List.size();i++){
  197.         List[i].r += P.r;
  198.     }
  199.     buildGraph();
  200.     CLR(vis,-1);
  201.     for(int i = 0;i<List.size();i++){
  202.         if(vis[i] == -1){
  203.             DP[i] = 0.0;
  204.             if(DFS(i, P)) return false;
  205.         }
  206.     }
  207.     return true;
  208. }
  209.  
  210. int main(){
  211.  
  212.     #ifdef forthright48
  213.     freopen ( "input.txt", "r", stdin );
  214.     //freopen ( "output A.txt", "w", stdout );
  215.     #else
  216.         freopen ( "out.in", "r", stdin );
  217.         freopen ( "out.out", "w", stdout );
  218.     #endif
  219.  
  220.     int N;
  221.     Point A;
  222.     scanf("%d",&N);
  223.     for(int i = 0;i<N;i++){
  224.         scanf("%lf %lf %lf",&A.x, &A.y, &A.r);
  225.         List.pb(A);
  226.     }
  227.     scanf("%lf %lf %lf",&A.x, &A.y, &A.r);
  228.     if(solve(A)) printf("YES\n");
  229.     else printf("NO\n");
  230. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement