#pragma GCC target("avx2") #pragma GCC optimize("Ofast,unroll-loops") #include #include #include typedef struct { int x, y; } point; double distance(point p, point q) { return sqrt((double)(p.x - q.x) * (p.x - q.x) + (double)(p.y - q.y) * (p.y - q.y)); } double area_of_triangle(point a, point b, point c) { double p, q, r, s; p = distance(a, b); q = distance(b, c); r = distance(c, a); s = (p + q + r) / 2.0; return sqrt(s * (s - p) * (s - q) * (s - r)); } typedef struct { double key; int id; } data; void merge_sort(int n, data x[]) { static data y[200001] = {}; if (n <= 1) return; merge_sort(n / 2, &(x[0])); merge_sort((n + 1) / 2, &(x[n/2])); int i, p, q; for (i = 0, p = 0, q = n / 2; i < n; i++) { if (p >= n / 2) y[i] = x[q++]; else if (q >= n) y[i] = x[p++]; else y[i] = (x[p].key < x[q].key)? x[p++]: x[q++]; } for (i = 0; i < n; i++) x[i] = y[i]; } void chmax(double* a, double b) { if (*a < b) *a = b; } int main() { struct timeval tt; double beg, cur; gettimeofday(&tt, NULL); beg = tt.tv_sec + (double)tt.tv_usec / 1000000; int i, N; point p[200001]; data d[200001]; scanf("%d", &N); for (i = 1, p[0].x = 0, p[0].y = 0; i <= N; i++) { scanf("%d %d", &(p[i].x), &(p[i].y)); d[i-1].key = distance(p[0], p[i]); d[i-1].id = i; } merge_sort(N, d); int j; double ans = 0.0; for (i = N - 1; i >= 0; i--) { for (j = i - 1; j >= 0; j--) { if (ans >= d[i].key * d[j].key * 0.5) break; chmax(&ans, area_of_triangle(p[0], p[i], p[j])); } gettimeofday(&tt, NULL); cur = tt.tv_sec + (double)tt.tv_usec / 1000000; if (cur - beg > 2.48) break; } printf("%lld\n", (long long)(ans * 2.0 + 0.5)); fflush(stdout); return 0; }