Advertisement
Guest User

Untitled

a guest
Oct 14th, 2012
244
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.52 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <ctime>
  5. #include <algorithm>
  6. #include <iostream>
  7. #include <vector>
  8. #include <list>
  9. #include <map>
  10. #include <set>
  11. #include <deque>
  12. #include <cassert>
  13. #include <math.h>
  14.  
  15. #define mp make_pair
  16. #define pb push_back
  17. #define sz(x) ((int)(x).size())
  18. #define taskname "restore"
  19.  
  20. #ifdef DEBUG
  21. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  22. #else
  23. #define eprintf(...)
  24. #endif
  25.  
  26. using namespace std;
  27.  
  28. typedef long long ll;
  29. typedef vector<ll> vll;
  30. typedef vector<int> vi;
  31. typedef vector<vi> vvi;
  32. typedef vector<bool> vb;
  33. typedef vector<vb> vvb;
  34. typedef pair<int, int> pii;
  35.  
  36. int mx, E[12], T[12], Cnt[55], MX[12][2], MY[12][2];
  37. pair <int, int> P[12][28000], X[12];
  38. int D[60], D2[61], ed;
  39. vector <pair <int, int> > V[58];
  40. int gcnt;
  41.  
  42. inline int fd (int v)
  43. {
  44.   int tmp=lower_bound(D,D+ed,v)-D;
  45.   return (D[tmp]==v)?(tmp):(-1);
  46. }
  47.  
  48. inline int dist (pair <int, int> a, pair <int, int> b)
  49. {
  50.   return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
  51. }
  52.  
  53. bool gen (int v)
  54. {
  55.   if (v==10)
  56.     return 1;
  57.   if (10-v>E[v])
  58.     return 0;
  59.  
  60.   bool fl;
  61.   int i, j, k;
  62.   for (E[v+1]=0, i=0; i<E[v]; i++)
  63.   {
  64.     MX[v+1][0]=max(MX[v][0],P[v][i].first), MX[v+1][1]=min(MX[v][1],P[v][i].first);
  65.     MY[v+1][0]=max(MY[v][0],P[v][i].second), MY[v+1][1]=min(MY[v][1],P[v][i].second);
  66.     if (MX[v+1][0]-MX[v+1][1]>10000 || MY[v+1][0]-MY[v+1][1]>10000)
  67.       continue;
  68.     for (fl=1, j=0; j<=v; j++)
  69.     {        
  70.       T[j]=fd(dist(P[v][i],X[j]));
  71.       if (T[j]==-1 || Cnt[T[j]]==0)
  72.       {
  73.         for (k=0; k<j; k++)
  74.           Cnt[T[k]]++;
  75.         fl=0;
  76.         break;
  77.       }
  78.       Cnt[T[j]]--;
  79.     }
  80.     if (fl)
  81.     {
  82.       P[v+1][E[v+1]++]=P[v][i];
  83.       for (k=0; k<=v; k++)
  84.         Cnt[T[k]]++;
  85.     }
  86.   }
  87.  
  88.   for (E[v+1]--; E[v+1]>=0; E[v+1]--)
  89.   {
  90.     for (X[v+1]=P[v+1][E[v+1]], i=0; i<=v; i++)
  91.       Cnt[fd(dist(X[v+1],X[i]))]--;
  92.  
  93.     MX[v+1][0]=max(MX[v][0],X[v + 1].first), MX[v+1][1]=min(MX[v][1],X[v + 1].first);
  94.     MY[v+1][0]=max(MY[v][0],X[v + 1].second), MY[v+1][1]=min(MY[v][1],X[v + 1].second);
  95.     if (gen(v+1))
  96.       return 1;
  97.     for (i=0; i<=v; i++)
  98.       Cnt[fd(dist(X[v+1],X[i]))]++;
  99.   }
  100.   return 0;
  101. }
  102.  
  103. int main() {
  104.   int i, j, x, y;
  105.   #ifdef DEBUG
  106.   clock_t __start__time__ = clock();
  107.   #endif
  108.  
  109.   freopen(taskname ".in", "r", stdin);
  110.   freopen(taskname ".out", "w", stdout);
  111.   for (i=0; i<55; i++) {
  112.     scanf("%d", &D[i]), D2[i]=D[i];
  113.     mx = max(mx, D[i]);
  114.   }
  115.   sort(D,D+55);
  116.   ed=unique(D,D+55)-D;
  117.   D[ed]=-1;
  118.   for (i=0; i<55; i++)
  119.     Cnt[fd(D2[i])]++;
  120.   for (i=0; i<ed; i++)
  121.     for (x=0; x*x<=D[i]; x++)
  122.     {
  123.       y=(int)(sqrt(D[i]+0.5));
  124.       while (y*y>D[i]-x*x && y>0)
  125.         y--;
  126.       while (y*y+x*x<D[i])
  127.         y++;
  128.       if (x*x+y*y==D[i])
  129.       {
  130.         V[i].pb(mp(x,y));
  131.         if (y!=0)
  132.           V[i].pb(mp(x,-y));
  133.         if (x!=0)
  134.         {
  135.           V[i].pb(mp(-x,y));
  136.           if (y!=0)
  137.             V[i].pb(mp(-x,-y));
  138.         }
  139.       }
  140.     }
  141.   for (i=ed-1; i>=0; i--)
  142.     if (Cnt[i]>0)
  143.       for (j=0; j<(int)V[i].size(); j++)
  144.         P[0][E[0]++]=V[i][j];
  145.   random_shuffle(P[0],P[0]+E[0]);
  146.   assert(gen(0));
  147.   int mx=-(int)1e6, my=-(int)1e6;
  148.   for (i=0; i<11; i++)
  149.     mx=max(mx,X[i].first), my=max(my,X[i].second);
  150.   for (i=0; i<11; i++)
  151.     printf("%d %d\n", 5000+X[i].first-mx, X[i].second+5000-my);
  152.   #ifdef DEBUG
  153.   eprintf("Work time: %.4lf\n", (double)(clock() - __start__time__) / CLOCKS_PER_SEC);
  154.   #endif
  155.   return 0;
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement