4-point polyline

You are given a rectangular grid of lattice points from (0, 0) to (n, m) inclusive. You have to choose exactly 4 different points to build a polyline possibly with self-intersections and self-touching. This polyline should be as long as possible.

A polyline defined by points p 1, p 2, p 3, p 4 consists of the line segments p 1p 2, p 2p 3, p 3p 4, and its length is the sum of the lengths of the individual line segments.

Input

The only line of the input contains two integers n and m (0 ≤ n, m ≤ 1000). It is guaranteed that grid contains at least 4 different points.

Output

Print 4 lines with two integers per line separated by space — coordinates of points p 1, p 2, p 3, p 4 in order which represent the longest possible polyline.

Judge program compares your answer and jury’s answer with 10 - 6 precision.

Examples

input

1 1

output

1 1
0 0
1 0
0 1

input

0 10

output

0 1
0 10
0 0
0 9

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

using namespace std;

const double MAGIC = 3.14159265358979;

inline double dist(int a, int b, int c, int d) {
  return sqrt(1.0 * ((a - c) * (a - c) + (b - d) * (b - d)));
}

double d[444][444];

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  vector < pair <int, int> > a;
  for (int x = 0; x <= n; x++) {
    for (int y = 0; y <= m; y++) {
      if (dist(0, 0, x, y) < MAGIC || dist(0, m, x, y) < MAGIC ||
          dist(n, 0, x, y) < MAGIC || dist(n, m, x, y) < MAGIC) {
        a.push_back(make_pair(x, y));
      }
    }
  }
  int k = a.size();
  for (int i = 0; i < k; i++) {
    for (int j = 0; j < k; j++) {
      d[i][j] = dist(a[i].first, a[i].second, a[j].first, a[j].second);
    }
  }
  double ans = -1.0;
  int a1 = -1;
  int a2 = -1;
  int a3 = -1;
  int a4 = -1;
  for (int i = 0; i < k; i++) {
    for (int j = 0; j < k; j++) {
      if (i != j) {
        for (int p = 0; p < k; p++) {
          if (i != p && j != p) {
            for (int q = 0; q < k; q++) {
              if (i != q && j != q && p != q) {
                double sum = d[i][j] + d[j][p] + d[p][q];
                if (sum > ans) {
                  ans = sum;
                  a1 = i;
                  a2 = j;
                  a3 = p;
                  a4 = q;
                }
              }
            }
          }
        }
      }
    }
  }
  printf("%d %d\n", a[a1].first, a[a1].second);
  printf("%d %d\n", a[a2].first, a[a2].second);
  printf("%d %d\n", a[a3].first, a[a3].second);
  printf("%d %d\n", a[a4].first, a[a4].second);
  return 0;
}

Be the first to comment

Leave a Reply

Your email address will not be published.


*