Advertisement
Guest User

Untitled

a guest
Jun 22nd, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.84 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <set>
  4. #include <map>
  5. #include <vector>
  6. #include <string>
  7. #include <cstring>
  8. #include <algorithm>
  9. #include <memory.h>
  10. #include <utility>
  11. #include <cassert>
  12. using namespace std;
  13.  
  14. #define forn( i,n ) for ( int i=0; i<(int)(n); i++ )
  15. #define pb push_back
  16. #define mp make_pair
  17. #define sz(a) (int)((a).size())
  18. typedef long long ll;
  19. typedef long double ld;
  20. typedef pair<int,int> pii;
  21.  
  22. char mm[266];
  23. int n, X0, Y0, x[410], y[410];
  24. int L[1010], R[1010];
  25.  
  26. bool LU()
  27. {
  28.   forn( i, n ) if ( x[i] > X0 || y[i] < Y0 ) return false;
  29.   return true;
  30. }
  31.  
  32. bool LD()
  33. {
  34.   forn( i, n ) if ( x[i] > X0 || y[i] > Y0 ) return false;
  35.   return true;
  36. }
  37.  
  38. bool RD()
  39. {
  40.   forn( i, n ) if ( x[i] < X0 || y[i] > Y0 ) return false;
  41.   return true;
  42. }
  43.  
  44. bool RU()
  45. {
  46.   forn( i, n ) if ( x[i] < X0 || y[i] < Y0 ) return false;
  47.   return true;
  48. }
  49.  
  50. void rotateLU()
  51. {
  52.   forn( i, n ) x[i] = 2*X0 - x[i];
  53.   mm['W'] = 'E';
  54.   mm['E'] = 'W';
  55. }
  56.  
  57. void rotateRD()
  58. {
  59.   forn( i, n ) y[i] = 2*Y0 - y[i];
  60.   mm['S'] = 'N';
  61.   mm['N'] = 'S';
  62. }
  63.  
  64. void rotateLD()
  65. {
  66.   rotateLU();
  67.   rotateRD();
  68. }
  69.  
  70. int main()
  71. {
  72.   scanf( "%d %d %d", &n, &X0, &Y0 );
  73.   forn( i, n ) scanf( "%d %d", &x[i], &y[i] );
  74.  
  75.   mm['N'] = 'N';
  76.   mm['S'] = 'S';
  77.   mm['W'] = 'W';
  78.   mm['E'] = 'E';
  79.  
  80.   if ( LU() ) rotateLU(); else
  81.   if ( LD() ) rotateLD(); else
  82.   if ( RD() ) rotateRD(); else
  83.     if ( !RU() )
  84.     {
  85.       printf( "-1\n" );
  86.       return 0;
  87.     }
  88.  
  89.   forn( i, n )
  90.   {
  91.     x[i] -= X0;
  92.     y[i] -= Y0;
  93. //    printf( "-> %d %d\n", x[i], y[i] );
  94.   }
  95.  
  96.   int rx = 0, ry = 1;
  97.  
  98.   forn( i, n )
  99.   {
  100.     rx = max( rx, x[i] );
  101.     ry = max( ry, y[i] );
  102.   }
  103.  
  104.   forn( i, 1000 ) L[i] = 10000, R[i] = -10000;
  105.  
  106.   L[0] = R[0] = 0;
  107.   forn( i, n )
  108.   {
  109.     int cur = y[i] == ry ? y[i] - 1 : y[i];
  110.     L[cur] = min( L[cur], x[i] );
  111.     R[cur] = max( R[cur], x[i] );
  112.   }
  113.  
  114.   for ( int i=ry-2; i>=0; i-- )
  115.     L[i] = min( L[i], L[i+1] );
  116.   for ( int i=1; i<ry; i++ )
  117.     R[i] = max( R[i], R[i-1] );
  118. /*
  119.   forn( i, ry )
  120.     printf( "%d %d\n", L[i], R[i] );
  121. */
  122.   forn( i, ry )
  123.   {
  124.     if ( L[i] > R[i] )
  125.     {
  126.       L[i] = L[i-1];
  127.       R[i] = R[i-1];
  128.     }
  129.  
  130.     if ( L[i] == R[i] )
  131.     {
  132.       if ( L[i] == 0 ) R[i]++; else
  133.       if ( R[i] == rx ) L[i]--; else
  134.         R[i]++;
  135.     }
  136.   }
  137.  
  138.   for ( int i=1; i<ry; i++ )
  139.     if ( L[i] >= R[i-1] ) R[i-1] = L[i]+1;
  140.  
  141.   int ans = 0;
  142.   forn( i, ry )
  143.     ans += R[i] - L[i];
  144.  
  145.   rx = R[ry-1];
  146.  
  147.   printf( "%d\n", ans );
  148.  
  149.   forn( i, ry-1 )
  150.   {
  151.     putchar( mm['N'] );
  152.     forn( q, L[i+1] - L[i] ) putchar( mm['E'] );
  153.   }
  154.   putchar( mm['N'] );
  155.   forn( q, rx-L[ry-1] ) putchar( mm['E'] );
  156.  
  157.   for ( int i=ry-1; i>0; i-- )
  158.   {
  159.     putchar( mm['S'] );
  160.     forn( q, R[i]-R[i-1] ) putchar( mm['W'] );
  161.   }
  162.   putchar( mm['S'] );
  163.   forn( q, R[0] ) putchar( mm['W'] );
  164.  
  165.   return 0;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement