Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <ctime>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #include <set>
- #include <map>
- #include <bitset>
- #include <queue>
- #include <complex>
- #include <cassert>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define fs first
- #define sc second
- #define sz(s) int((s).size())
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #define next _next
- #define prev _prev
- #define rank _rank
- #define y0 _fjldkl
- typedef long long ll;
- typedef long long llong;
- typedef unsigned int uint;
- typedef unsigned long long ull;
- typedef vector <int> vi;
- typedef pair <int, int> pii;
- typedef complex <double> tc;
- const int inf = int(1e9);
- const double eps = 1e-9;
- const double pi = 4 * atan(double(1));
- const int diff = 3;
- const int max_deep = 15;
- const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
- const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
- struct state{
- int x[4], y[4];
- };
- int ans, x0, y0;
- inline bool bad(state &cur, int x, int y){
- pii p = mp(x, y);
- for(int i = 1; i < 4; i++){
- if(mp(cur.x[i], cur.y[i]) == p){
- return true;
- }
- }
- return false;
- }
- inline bool fight(state &cur, int x, int y){
- for(int i = 1; i < 4; i++){
- if(cur.x[i] == x || cur.y[i] == y){
- return true;
- }
- }
- return false;
- }
- inline bool can(state &cur){
- vector <pii> lst;
- for(int i = 0; i < 4; i++){
- lst.pb(mp(cur.x[i], cur.y[i]));
- }
- sort(lst.begin(), lst.end());
- if(unique(lst.begin(), lst.end()) != lst.end()){
- return false;
- }
- bool fl = false;
- for(int i = 0; i < 8; i++){
- int x = cur.x[0] + dx[i], y = cur.y[0] + dy[i];
- if(bad(cur, x, y)){
- return false;
- }
- if(!fight(cur, x, y)){
- fl = true;
- }
- }
- if(!fl){
- return false;
- }
- return true;
- }
- inline bool over(state &cur){
- for(int i = 0; i < 8; i++){
- if(bad(cur, cur.x[0] + dx[i], cur.y[0] + dy[i])){
- return false;
- }
- }
- if(!fight(cur, cur.x[0], cur.y[0])){
- return false;
- }
- bool fl = false;
- for(int i = 0; i < 8; i++){
- if(!fight(cur, cur.x[0] + dx[i], cur.y[0] + dy[i])){
- return false;
- }
- }
- return true;
- }
- void gen(state &cur, int step, int deep){
- if(deep >= ans){
- return;
- }
- if(step == 0){
- for(int i = 1; i < 4; i++){
- for(int j = -diff; j <= diff; j++){
- int oy = cur.y[i];
- cur.y[i] = y0 + j;
- if(over(cur)){
- ans = deep + 1;
- cur.y[i] = oy;
- return;
- }
- if(y0 + j != oy && can(cur)){
- gen(cur, 1 - step, deep + 1);
- }
- cur.y[i] = oy;
- int ox = cur.x[i];
- cur.x[i] = x0 + j;
- if(over(cur)){
- ans = deep + 1;
- cur.x[i] = ox;
- return;
- }
- if(x0 + j != ox && can(cur)){
- gen(cur, 1 - step, deep + 1);
- }
- cur.x[i] = ox;
- }
- }
- }
- else{
- for(int i = 0; i < 8; i++){
- cur.x[0] += dx[i];
- cur.y[0] += dy[i];
- if(!fight(cur, cur.x[0], cur.y[0])){
- gen(cur, 1 - step, deep + 1);
- }
- cur.x[0] -= dx[i];
- cur.y[0] -= dy[i];
- }
- }
- }
- void go(state &cur){
- x0 = cur.x[0];
- y0 = cur.y[0];
- int best_ans = inf, a = -1, b = -1, c = -1;
- for(int i = 1; i < 4; i++){
- for(int j = -diff; j <= diff; j++){
- int oy = cur.y[i];
- cur.y[i] = y0 + j;
- if(over(cur)){
- cout << i << " " << 0 << " " << y0 + j - oy << endl;
- return;
- }
- if(y0 + j != oy && can(cur)){
- ans = max_deep;
- gen(cur, 1, 0);
- if(ans < best_ans){
- ans = best_ans;
- a = i;
- b = j;
- c = 0;
- }
- }
- cur.y[i] = oy;
- int ox = cur.x[i];
- cur.x[i] = x0 + j;
- if(over(cur)){
- cout << i << " " << x0 + j - ox << " " << 0 << endl;
- return;
- }
- if(x0 + j != ox && can(cur)){
- ans = max_deep;
- gen(cur, 1, 0);
- if(ans < best_ans){
- ans = best_ans;
- a = i;
- b = j;
- c = 1;
- }
- }
- cur.x[i] = ox;
- }
- }
- if(c == 0){
- cout << a << " " << 0 << " " << y0 + b - cur.y[0] << endl;
- cur.y[a] = y0 + b;
- }
- else{
- cout << a << " " << x0 + b - cur.x[0] << " " << 0 << endl;
- cur.x[a] = x0 + b;
- }
- int vx, vy;
- cin >> vx >> vy;
- cur.x[0] += vx;
- cur.y[0] += vy;
- go(cur);
- }
- int main(){
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- //freopen("sum.in", "r", stdin);
- //freopen("sum.out", "w", stdout);
- state cur;
- for(int i = 0; i < 4; i++){
- cin >> cur.x[i] >> cur.y[i];
- }
- go(cur);
- return 0;
- }
Add Comment
Please, Sign In to add comment