Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <algorithm>
- #include <iostream>
- #include <vector>
- #include <list>
- #include <map>
- #include <set>
- #include <deque>
- #include <cassert>
- #include <math.h>
- #define mp make_pair
- #define pb push_back
- #define sz(x) ((int)(x).size())
- #define taskname "restore"
- #ifdef DEBUG
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #else
- #define eprintf(...)
- #endif
- using namespace std;
- typedef long long ll;
- typedef vector<ll> vll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<bool> vb;
- typedef vector<vb> vvb;
- typedef pair<int, int> pii;
- int mx, E[12], T[12], Cnt[55], MX[12][2], MY[12][2];
- pair <int, int> P[12][28000], X[12];
- int D[60], D2[61], ed;
- vector <pair <int, int> > V[58];
- int gcnt;
- inline int fd (int v)
- {
- int tmp=lower_bound(D,D+ed,v)-D;
- return (D[tmp]==v)?(tmp):(-1);
- }
- inline int dist (pair <int, int> a, pair <int, int> b)
- {
- return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
- }
- bool gen (int v)
- {
- if (v==10)
- return 1;
- if (10-v>E[v])
- return 0;
- bool fl;
- int i, j, k;
- for (E[v+1]=0, i=0; i<E[v]; i++)
- {
- MX[v+1][0]=max(MX[v][0],P[v][i].first), MX[v+1][1]=min(MX[v][1],P[v][i].first);
- MY[v+1][0]=max(MY[v][0],P[v][i].second), MY[v+1][1]=min(MY[v][1],P[v][i].second);
- if (MX[v+1][0]-MX[v+1][1]>10000 || MY[v+1][0]-MY[v+1][1]>10000)
- continue;
- for (fl=1, j=0; j<=v; j++)
- {
- T[j]=fd(dist(P[v][i],X[j]));
- if (T[j]==-1 || Cnt[T[j]]==0)
- {
- for (k=0; k<j; k++)
- Cnt[T[k]]++;
- fl=0;
- break;
- }
- Cnt[T[j]]--;
- }
- if (fl)
- {
- P[v+1][E[v+1]++]=P[v][i];
- for (k=0; k<=v; k++)
- Cnt[T[k]]++;
- }
- }
- for (E[v+1]--; E[v+1]>=0; E[v+1]--)
- {
- for (X[v+1]=P[v+1][E[v+1]], i=0; i<=v; i++)
- Cnt[fd(dist(X[v+1],X[i]))]--;
- MX[v+1][0]=max(MX[v][0],X[v + 1].first), MX[v+1][1]=min(MX[v][1],X[v + 1].first);
- MY[v+1][0]=max(MY[v][0],X[v + 1].second), MY[v+1][1]=min(MY[v][1],X[v + 1].second);
- if (gen(v+1))
- return 1;
- for (i=0; i<=v; i++)
- Cnt[fd(dist(X[v+1],X[i]))]++;
- }
- return 0;
- }
- int main() {
- int i, j, x, y;
- #ifdef DEBUG
- clock_t __start__time__ = clock();
- #endif
- freopen(taskname ".in", "r", stdin);
- freopen(taskname ".out", "w", stdout);
- for (i=0; i<55; i++) {
- scanf("%d", &D[i]), D2[i]=D[i];
- mx = max(mx, D[i]);
- }
- sort(D,D+55);
- ed=unique(D,D+55)-D;
- D[ed]=-1;
- for (i=0; i<55; i++)
- Cnt[fd(D2[i])]++;
- for (i=0; i<ed; i++)
- for (x=0; x*x<=D[i]; x++)
- {
- y=(int)(sqrt(D[i]+0.5));
- while (y*y>D[i]-x*x && y>0)
- y--;
- while (y*y+x*x<D[i])
- y++;
- if (x*x+y*y==D[i])
- {
- V[i].pb(mp(x,y));
- if (y!=0)
- V[i].pb(mp(x,-y));
- if (x!=0)
- {
- V[i].pb(mp(-x,y));
- if (y!=0)
- V[i].pb(mp(-x,-y));
- }
- }
- }
- for (i=ed-1; i>=0; i--)
- if (Cnt[i]>0)
- for (j=0; j<(int)V[i].size(); j++)
- P[0][E[0]++]=V[i][j];
- random_shuffle(P[0],P[0]+E[0]);
- assert(gen(0));
- int mx=-(int)1e6, my=-(int)1e6;
- for (i=0; i<11; i++)
- mx=max(mx,X[i].first), my=max(my,X[i].second);
- for (i=0; i<11; i++)
- printf("%d %d\n", 5000+X[i].first-mx, X[i].second+5000-my);
- #ifdef DEBUG
- eprintf("Work time: %.4lf\n", (double)(clock() - __start__time__) / CLOCKS_PER_SEC);
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement