Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pb push_back
- #define nl puts ("")
- #define sp printf ( " " )
- #define phl printf ( "hello\n" )
- #define ff first
- #define ss second
- #define POPCOUNT __builtin_popcountll
- #define RIGHTMOST __builtin_ctzll
- #define LEFTMOST(x) (63-__builtin_clzll((x)))
- #define MP make_pair
- #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
- #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
- #define CLR(x,y) memset(x,y,sizeof(x))
- #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
- #define MIN(a,b) ((a)<(b)?(a):(b))
- #define MAX(a,b) ((a)>(b)?(a):(b))
- #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
- #define SQ(x) ((x)*(x))
- #define ABS(x) ((x)<0?-(x):(x))
- #define FABS(x) ((x)+eps<0?-(x):(x))
- #define ALL(x) (x).begin(),(x).end()
- #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
- #define SZ(x) ((vlong)(x).size())
- #define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
- #define MOD(x,y) (((x)*(y))%mod)
- #define ODD(x) (((x)&1)==0?(0):(1))
- #define Set(N,cur) N=(N|(1<<cur))
- #define Reset(N,cur) N=(N&(~(1<<cur)))
- #define Check(N,cur) (!((N&(1<<cur))==0))
- #define dbgA(A,i) debug("At pos: ",i," = ",A[i])
- #define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
- #ifdef forthright48
- #include <ctime>
- clock_t tStart = clock();
- #define debug(args...) {dbg,args; cerr<<endl;}
- #define timeStamp debug ("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
- #define bug printf("%d\n",__LINE__);
- #else
- #define debug(args...) // Just strip off all debug tokens
- #define timeStamp
- #endif
- struct debugger{
- template<typename T> debugger& operator , (const T& v){
- cerr<<v<<" ";
- return *this;
- }
- }dbg;
- #define LL long long
- #define LLU long long unsigned int
- typedef long long vlong;
- typedef unsigned long long uvlong;
- typedef pair < int, int > pii;
- typedef pair < vlong, vlong > pll;
- inline vlong gcd ( vlong a, vlong b ) {
- a = ABS ( a ); b = ABS ( b );
- while ( b ) { a = a % b; swap ( a, b ); } return a;
- }
- vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
- vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
- x2 = 1; y2 = 0; x1 = 0; y1 = 1;
- for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
- q = r2 / r1; r = r2 % r1;
- x = x2 - (q * x1); y = y2 - (q * y1);
- }
- *X = x2; *Y = y2;
- return r2;
- }
- inline vlong modInv ( vlong a, vlong m ) {
- vlong x, y;
- ext_gcd( a, m, &x, &y );
- x %= m;
- if ( x < 0 ) x += m;
- return x;
- }
- inline vlong power ( vlong a, vlong p ) {
- vlong res = 1, x = a;
- while ( p ) {
- if ( p & 1 ) res = ( res * x );
- x = ( x * x ); p >>= 1;
- }
- return res;
- }
- inline vlong bigmod ( vlong a, vlong p, vlong m ) {
- vlong res = 1 % m, x = a % m;
- while ( p ) {
- if ( p & 1 ) res = ( res * x ) % m;
- x = ( x * x ) % m; p >>= 1;
- }
- return res;
- }
- inline int STRLEN(char *s){
- int p = 0; while(s[p]) p++; return p;
- }
- inline LL SQRT(LL a){
- LL v = sqrt(a);
- if(SQ(v) == a) return v;
- else if(SQ(v+1) == a) return v+1;
- else if(SQ(v+2) == a) return v+2;
- else return -1; /// a can no be written as p^2
- }
- //int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
- //int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
- //int dir8[8][2] = {{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{1,1},{1,-1},{-1,1}};
- const LL inf = 10000000000000000LL;
- const double pi = 2 * acos ( 0.0 );
- const double eps = 1e-8;
- ///========================= TEMPLATE ENDS HERE ========================///
- ///=======================================================================///
- #define Size 355
- struct Point {
- double x, y, r;
- };
- vector<Point> List;
- double DP[Size];
- int vis[Size];
- vector<int> Graph[Size];
- /// Compute A dot B:
- double dot(Point A, Point B){
- return (A.x * B.x + A.y * B.y);
- }
- ///Compute AB dot AC
- double dotProduct(Point A, Point B, Point C) {
- Point AB = {B.x - A.x, B.y - A.y}; /// AB vector
- Point AC = {C.x - A.x, C.y - A.y}; /// AC vector
- return dot(AB, AC);
- }
- double dist(Point A, Point B) {
- return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
- }
- /// Angel between vector (A-B) and (A-C)
- double getAngel(Point A, Point B, Point C){
- double dotVal = dotProduct(A, B, C);
- double a = dotVal/(dist(A,B) * dist(A,C));
- if(a < -1.0) a = -1.0;
- if(a > 1.0) a = 1.0;
- return acos(a);
- }
- bool DFS(int cur, Point P){
- vis[cur] = 1;
- for(int i = 0;i<Graph[cur].size();i++){
- int v = Graph[cur][i];
- double a = DP[cur] + getAngel(P, List[v], List[cur]);
- if(vis[v] == -1){
- DP[v] = a;
- bool ret = DFS(v, P);
- if(ret == true) return true;
- }else{
- double dif = a - DP[v];
- if(dif+eps > 2.0*pi || dif < -2.0*pi+eps) return true;
- }
- }
- return false;
- }
- void buildGraph(){
- for(int i = 0;i<List.size();i++){
- for(int j = i+1;j<List.size();j++){
- double d = dist(List[i],List[j]);
- double r = List[i].r + List[j].r;
- if(r>d+eps){
- Graph[i].pb(j);
- Graph[j].pb(i);
- }
- }
- }
- }
- bool solve(Point P){
- for(int i = 0;i<List.size();i++){
- List[i].r += P.r;
- }
- buildGraph();
- CLR(vis,-1);
- for(int i = 0;i<List.size();i++){
- if(vis[i] == -1){
- DP[i] = 0.0;
- if(DFS(i, P)) return false;
- }
- }
- return true;
- }
- int main(){
- #ifdef forthright48
- //freopen ( "input.txt", "r", stdin );
- //freopen ( "output A.txt", "w", stdout );
- #else
- freopen ( "out.in", "r", stdin );
- freopen ( "out.out", "w", stdout );
- #endif
- int N;
- Point A;
- scanf("%d",&N);
- for(int i = 0;i<N;i++){
- scanf("%lf %lf %lf",&A.x, &A.y, &A.r);
- List.pb(A);
- }
- scanf("%lf %lf %lf",&A.x, &A.y, &A.r);
- if(solve(A)) printf("YES\n");
- else printf("NO\n");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement