SPOJ/MLE.cc

   1 #define LOCAL
   2
   3 /** template.h ver 0.5.1 */
   4
   5 #include <cassert>
   6 #include <cctype>
   7 #include <cmath>
   8 #include <cstdio>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <ctime>
  12 #include <deque>
  13 #include <list>
  14 #include <map>
  15 #include <queue>
  16 #include <set>
  17 #include <stack>
  18 #include <vector>
  19 #include <fstream>
  20 #include <iomanip>
  21 #include <iostream>
  22 #include <sstream>
  23 #include <algorithm>
  24 #include <bitset>
  25 #include <complex>
  26 #include <functional>
  27 #include <limits>
  28 #include <numeric>
  29 #include <string>
  30 #include <typeinfo>
  31 #include <utility>
  32 #include <valarray>
  33
  34 #define REP(i, n) for (int i = 0; i < int(n); ++i)
  35 #define FOR(i, a, b) for (int i = int(a); i < int(b); ++i)
  36 #define DWN(i, b, a) for (int i = int(b - 1); i >= int(a); --i)
  37 #define REP_1(i, n) for (int i = 1; i <= int(n); ++i)
  38 #define FOR_1(i, a, b) for (int i = int(a); i <= int(b); ++i)
  39 #define DWN_1(i, b, a) for (int i = int(b); i >= int(a); --i)
  40 #define REP_C(i, n) for (int n____ = int(n), i = 0; i < n____; ++i)
  41 #define FOR_C(i, a, b) for (int b____ = int(b), i = a; i < b____; ++i)
  42 #define DWN_C(i, b, a) for (int a____ = int(a), i = b - 1; i >= a____; --i)
  43 #define REP_N(i, n) for (i = 0; i < int(n); ++i)
  44 #define FOR_N(i, a, b) for (i = int(a); i < int(b); ++i)
  45 #define DWN_N(i, b, a) for (i = int(b - 1); i >= int(a); --i)
  46 #define REP_1_C(i, n) for (int n____ = int(n), i = 1; i <= n____; ++i)
  47 #define FOR_1_C(i, a, b) for (int b____ = int(b), i = a; i <= b____; ++i)
  48 #define DWN_1_C(i, b, a) for (int a____ = int(a), i = b; i >= a____; --i)
  49 #define REP_1_N(i, n) for (i = 1; i <= int(n); ++i)
  50 #define FOR_1_N(i, a, b) for (i = int(a); i <= int(b); ++i)
  51 #define DWN_1_N(i, b, a) for (i = int(b); i >= int(a); --i)
  52 #define REP_C_N(i, n) for (n____ = int(n), i = 0; i < n____; ++i)
  53 #define FOR_C_N(i, a, b) for (b____ = int(b), i = a; i < b____; ++i)
  54 #define DWN_C_N(i, b, a) for (a____ = int(a), i = b - 1; i >= a____; --i)
  55 #define REP_1_C_N(i, n) for (n____ = int(n), i = 1; i <= n____; ++i)
  56 #define FOR_1_C_N(i, a, b) for (b____ = int(b), i = a; i <= b____; ++i)
  57 #define DWN_1_C_N(i, b, a) for (a____ = int(a), i = b; i >= a____; --i)
  58
  59 #define ECH(it, A) for (__typeof(A.begin()) it = A.begin(); it != A.end(); ++it)
  60 #define REP_S(it, str) for (char *it = str; *it; ++it)
  61 #define REP_G(it, u) for (int it = adj[u]; it!= -1; it = next[it])
  62 #define DO(n) for (int ____n ## __line__ = n; ____n ## __line__ -- ;)
  63 #define REP_2(i, j, n, m) REP(i, n) REP(j, m)
  64 #define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)
  65 #define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)
  66 #define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)
  67
  68 #define COPY(a, b) memcpy(a, b, sizeof a)
  69 #define Rush int T____; RD(T____); DO(T____)
  70 #define Display(A, n, m) {                   \
  71   REP(i, n) {                                \
  72     REP(j, m) std::cout << A[i][j] << " ";   \
  73     std::cout << endl;                       \
  74   }                                          \
  75 }
  76
  77 #define Display_1(A, n, m) {                 \
  78   REP_1(i, n) {                              \
  79     REP_1(j, m) std::cout << A[i][j] << " "; \
  80     std::cout << endl;                       \
  81   }                                          \
  82 }
  83 #pragma comment(linker, "/STACK:16777216")
  84
  85 typedef unsigned uint;
  86 typedef long long int64;
  87 typedef unsigned long long uint64;
  88
  89 const int dx[] = {-1, 0, 1, 0};
  90 const int dy[] = {0, 1, 0, -1};
  91
  92 const int MOD = 1000000007;
  93 //const int INF = 0x3f3f3f3f;
  94 const int64 INF = 1LL << 62;
  95 const double eps = 1e-9;
  96 const double oo = 1e20;
  97
  98 #ifdef M_PI
  99 const double PI = M_PI;
 100 #else
 101 const double PI = acos(-1.0);
 102 #endif
 103
 104 template <typename T> inline T& RD(T &);
 105 template <typename T> inline void OT(const T &);
 106 inline int64 RD() { int64 x; return RD(x); }
 107 inline char& RC(char &c) { scanf(" %c", &c); return c; }
 108 inline char RC() { char c; return RC(c); }
 109 //inline char& RC(char &c){ c = getchar(); return c; }
 110 //inline char RC(){ return getchar(); }
 111 inline double& RF(double &x) { scanf("%lf", &x); return x; }
 112 inline double RF() { double x; return RF(x); }
 113 inline char* RS(char *s) { scanf("%s", s); return s; }
 114
 115 template <typename T0, typename T1> inline T0& RD(T0 &x0, T1 &x1) { RD(x0), RD(x1); return x0; }
 116 template <typename T0, typename T1, typename T2> inline T0& RD(T0 &x0, T1 &x1, T2 &x2) { RD(x0), RD(x1), RD(x2); return x0; }
 117 template <typename T0, typename T1, typename T2, typename T3> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) { RD(x0), RD(x1), RD(x2), RD(x3); return x0; }
 118 template <typename T0, typename T1, typename T2, typename T3, typename T4> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) { RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0; }
 119 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) { RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0; }
 120 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) { RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0; }
 121 template <typename T0, typename T1> inline void OT(const T0 &x0, const T1 &x1) { OT(x0), OT(x1); }
 122 template <typename T0, typename T1, typename T2> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) { OT(x0), OT(x1), OT(x2); }
 123 template <typename T0, typename T1, typename T2, typename T3> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) { OT(x0), OT(x1), OT(x2), OT(x3); }
 124 template <typename T0, typename T1, typename T2, typename T3, typename T4> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4) { OT(x0), OT(x1), OT(x2), OT(x3), OT(x4); }
 125 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5) { OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5); }
 126 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5, const T6 &x6) { OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6); }
 127 inline char& RC(char &a, char &b) { RC(a), RC(b); return a; }
 128 inline char& RC(char &a, char &b, char &c) { RC(a), RC(b), RC(c); return a; }
 129 inline char& RC(char &a, char &b, char &c, char &d) { RC(a), RC(b), RC(c), RC(d); return a; }
 130 inline char& RC(char &a, char &b, char &c, char &d, char &e) { RC(a), RC(b), RC(c), RC(d), RC(e); return a; }
 131 inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f) { RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a; }
 132 inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) { RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a; }
 133 inline double& RF(double &a, double &b) { RF(a), RF(b); return a; }
 134 inline double& RF(double &a, double &b, double &c) { RF(a), RF(b), RF(c); return a; }
 135 inline double& RF(double &a, double &b, double &c, double &d) { RF(a), RF(b), RF(c), RF(d); return a; }
 136 inline double& RF(double &a, double &b, double &c, double &d, double &e) { RF(a), RF(b), RF(c), RF(d), RF(e); return a; }
 137 inline double& RF(double &a, double &b, double &c, double &d, double &e, double &f) { RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a; }
 138 inline double& RF(double &a, double &b, double &c, double &d, double &e, double &f, double &g) { RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a; }
 139 inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
 140 inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
 141
 142 template <typename T> inline void RST(T &A) { memset(A, 0, sizeof(A)); }
 143 template <typename T0, typename T1> inline void RST(T0 &A0, T1 &A1) { RST(A0), RST(A1); }
 144 template <typename T0, typename T1, typename T2> inline void RST(T0 &A0, T1 &A1, T2 &A2) { RST(A0), RST(A1), RST(A2); }
 145 template <typename T0, typename T1, typename T2, typename T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) { RST(A0), RST(A1), RST(A2), RST(A3); }
 146 template <typename T0, typename T1, typename T2, typename T3, typename T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) { RST(A0), RST(A1), RST(A2), RST(A3), RST(A4); }
 147 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) { RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5); }
 148 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) { RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6); }
 149 template <typename T> inline void FILL(T &A, int x) { memset(A, x, sizeof(A)); }
 150 template <typename T0, typename T1> inline void FILL(T0 &A0, T1 &A1, int x) { FILL(A0, x), FILL(A1, x); }
 151 template <typename T0, typename T1, typename T2> inline void FILL(T0 &A0, T1 &A1, T2 &A2, int x) { FILL(A0, x), FILL(A1, x), FILL(A2, x); }
 152 template <typename T0, typename T1, typename T2, typename T3> inline void FILL(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) { FILL(A0, x), FILL(A1, x), FILL(A2, x), FILL(A3, x); }
 153 template <typename T0, typename T1, typename T2, typename T3, typename T4> inline void FILL(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) { FILL(A0, x), FILL(A1, x), FILL(A2, x), FILL(A3, x), FILL(A4, x); }
 154 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> inline void FILL(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) { FILL(A0, x), FILL(A1, x), FILL(A2, x), FILL(A3, x), FILL(A4, x), FILL(A5, x); }
 155 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> inline void FILL(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) { FILL(A0, x), FILL(A1, x), FILL(A2, x), FILL(A3, x), FILL(A4, x), FILL(A5, x), FILL(A6, x); }
 156 template <typename T> inline void CLR(std::priority_queue <T, std::vector <T> , std::less <T> > &q) { while (!q.empty()) q.pop(); }
 157 template <typename T> inline void CLR(std::priority_queue <T, std::vector <T> , std::greater <T> > &q) { while (!q.empty()) q.pop(); }
 158 template <typename T> inline void CLR(T &A) { A.clear(); }
 159 template <typename T0, typename T1> inline void CLR(T0 &A0, T1 &A1) { CLR(A0), CLR(A1); }
 160 template <typename T0, typename T1, typename T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2) { CLR(A0), CLR(A1), CLR(A2); }
 161 template <typename T0, typename T1, typename T2, typename T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) { CLR(A0), CLR(A1), CLR(A2), CLR(A3); }
 162 template <typename T0, typename T1, typename T2, typename T3, typename T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) { CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4); }
 163 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) { CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5); }
 164 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) { CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6); }
 165 template <typename T> inline void CLR(T &A, int n) { REP(i, n) CLR(A[i]); }
 166
 167 template <typename T> inline void cmax(T &x, T ano) { if (!(ano < x)) x = ano; }
 168 template <typename T> inline void cmin(T &x, T ano) { if (ano < x) x = ano; }
 169 template <typename T> inline T sqr(T x) { return x * x; }
 170
 171 namespace BO {
 172
 173 inline bool _1(int x, int i) { return bool(x&1 << i); }
 174 inline bool _1(int64 x, int i) { return bool(x&1LL << i); }
 175 inline int64 _1(int i) { return 1LL << i; }
 176 inline int64 _U(int i) { return _1(i) - 1; }
 177 inline int reverse_bits(int x) {
 178   x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
 179   x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
 180   x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
 181   x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
 182   x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
 183   return x;
 184 }
 185 inline int64 reverse_bits(int64 x) {
 186   x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
 187   x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
 188   x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
 189   x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
 190   x = ((x >> 16) & 0x0000ffff0000ffffLL) | ((x << 16) & 0xffff0000ffff0000LL);
 191   x = ((x >> 32) & 0x00000000ffffffffLL) | ((x << 32) & 0xffffffff00000000LL);
 192   return x;
 193 }
 194 template <typename T> inline bool odd(T x) { return x&1; }
 195 template <typename T> inline bool even(T x) { return !odd(x); }
 196 } using namespace BO;
 197
 198 namespace NT {
 199
 200 inline void INC(int &a, int b) { a += b; if (a >= MOD) a -= MOD; }
 201 inline int sum(int a, int b) { a += b; if (a >= MOD) a -= MOD; return a; }
 202 inline void DEC(int &a, int b) { a -= b; if (a < 0) a += MOD; }
 203 inline int dif(int a, int b) { a -= b; if (a < 0) a += MOD; return a; }
 204 inline void MUL(int &a, int b) { a = (int64)a * b % MOD; }
 205 inline int pdt(int a, int b) { return (int64)a * b % MOD; }
 206 inline int sum(int a, int b, int c) { return sum(sum(a, b), c); }
 207 inline int sum(int a, int b, int c, int d) { return sum(sum(a, b), sum(c, d)); }
 208 inline int pdt(int a, int b, int c) {return pdt(pdt(a, b), c); }
 209 inline int pdt(int a, int b, int c, int d) {return pdt(pdt(pdt(a, b), c), d); }
 210
 211 template <typename T>
 212 inline T pow(T a, int64 b) {
 213   T c(1);
 214   while (b) {
 215     if (b & 1) c *= a;
 216     a *= a, b >>= 1;
 217   }
 218   return c;
 219 }
 220
 221 inline int _I(int b) {
 222   int a = MOD, x1 = 0, x2 = 1, q;
 223   while (true) {
 224     q = a / b, a %= b;
 225     if (!a) return (x2 + MOD) % MOD;
 226     DEC(x1, pdt(q, x2));
 227     q = b / a, b %= a;
 228     if (!b) return (x1 + MOD) % MOD;
 229     DEC(x2, pdt(q, x1));
 230   }
 231 }
 232
 233 inline void DIV(int &a, int b) { MUL(a, _I(b)); }
 234 inline int qtt(int a, int b) { return pdt(a, _I(b)); }
 235
 236 inline int phi(int n) {
 237   int res = n;
 238   for (int i = 2; sqr(i) <= n; ++i) {
 239     if (!(n % i)) {
 240       DEC(res, qtt(res, i));
 241       do { n /= i; } while(!(n % i));
 242     }
 243   }
 244   if (n != 1) DEC(res, qtt(res, n));
 245   return res;
 246 }
 247
 248 template <typename T>
 249 T gcd(T a, T b) {
 250   for (T r; r = a % b; a = b, b = r) {}
 251   return b;
 252 }
 253
 254 } using namespace NT;
 255
 256 namespace RANDOM {
 257
 258 inline uint rand16() { return ((bool)(rand()&1) << 15) | rand(); }
 259 inline uint rand32() { return (rand16() << 16) | rand16(); }
 260 inline uint64 rand64() { return ((int64)rand32() << 32) | rand32(); }
 261 inline uint64 random(int64 l, int64 r) { return rand64() % (r - l) + l; }
 262 inline uint dice() { return random(1, 6); }
 263 bool coin() { return rand() & 1; }
 264
 265 } using namespace RANDOM;
 266
 267 namespace CLOCK {
 268
 269 double s0, s1, rd, T;
 270 inline double getTime() {
 271 #ifdef LOCAL
 272   return 1.0 * clock() / CLOCKS_PER_SEC;
 273 #else
 274   timeval tv;
 275   gettimeofday(&tv, 0);
 276   return tv.tv_sec + tv.tv_usec * 1e-6;
 277 #endif
 278 }
 279 inline double elapsed() { return getTime() - s0; }
 280
 281 } //using namespace CLOCK;
 282
 283 template <typename T>
 284 inline T& RD(T &x) {
 285   static char c;
 286   static bool flag;
 287   flag = false;
 288   for (c = getchar(); !isdigit(c) && c != '-'; c = getchar()) {}
 289   if (c == '-') flag = true, c = getchar();
 290   x = c - '0';
 291   for (c = getchar(); isdigit(c); c = getchar()) x = x * 10 + c - '0';
 292   if (flag) x = -x;
 293   return x;
 294 }
 295
 296 template <typename T> inline void OT(const T& x) {
 297   printf("%lld\n", x);
 298   //printf("%.2lf\n", x);
 299 }
 300 /** end of template **/
 301
 302 /* --------------------------------------------------------------------------------- */
 303
 304 #define fst first
 305 #define snd second
 306
 307 const int N = 100000 + 10;
 308
 309 int n;
 310 std::pair<int, int> point[N], tmp[N];
 311
 312 struct node {
 313   node *ch[2];
 314   std::pair<int, int> location;
 315 } pool[N], *tot;
 316
 317 inline bool cmpx(const std::pair<int, int>& a, const std::pair<int, int>& b) {
 318   return a.fst < b.fst;
 319 }
 320
 321 inline bool cmpy(const std::pair<int, int>& a, const std::pair<int, int>& b) {
 322   return a.snd < b.snd;
 323 }
 324
 325 typedef bool (*cmpfunc)(const std::pair<int, int>&, const std::pair<int, int>&);
 326
 327 inline cmpfunc cmp(int dep) { return odd(dep) ? cmpx : cmpy; }
 328
 329 node* kdtree(int dep, int st, int ed) {
 330   if (st > ed) return NULL;
 331   std::sort(tmp + st, tmp + ed + 1, cmp(dep));
 332   int mid = (st + ed) / 2;
 333   node* cur = tot++;
 334   cur->location = tmp[mid];
 335   cur->ch[0] = kdtree(dep + 1, st, mid - 1);
 336   cur->ch[1] = kdtree(dep + 1, mid + 1, ed);
 337   return cur;
 338 }
 339
 340 inline int64 dist(const std::pair<int, int>& a, const std::pair<int, int>& b) {
 341   return sqr((int64)a.fst - b.fst) + sqr((int64)a.snd - b.snd);
 342 }
 343
 344 int64 ans;
 345
 346 void nearest(node *cur, int dep, const std::pair<int, int>& p) {
 347   if (!cur) return;
 348   cmpfunc cmpf = cmp(dep);
 349   bool d = cmpf(cur->location, p);
 350   if (cur->location != p) cmin(ans, dist(cur->location, p));
 351   nearest(cur->ch[d], dep + 1, p);
 352   if (cmpf == cmpx) {
 353     if (sqr((int64)cur->location.fst - p.fst) <= ans)
 354       nearest(cur->ch[d^1], dep + 1, p);
 355   } else {
 356     if (sqr((int64)cur->location.snd - p.snd) <= ans)
 357       nearest(cur->ch[d^1], dep + 1, p);
 358   }
 359 }
 360
 361 int main() {
 362 #ifndef ONLINE_JUDGE
 363   freopen("in.txt", "r", stdin);
 364   freopen("out.txt", "w", stdout);
 365 #endif
 366   Rush {
 367     RD(n);
 368     REP_1(i, n) RD(point[i].fst, point[i].snd);
 369     COPY(tmp, point);
 370     tot = pool;
 371     node *root = kdtree(1, 1, n);
 372     REP_1(i, n) {
 373       ans = INF;
 374       nearest(root, 1, point[i]);
 375       OT(ans);
 376     }
 377   }
 378   return 0;
 379 }