#include #include #include typedef struct { long double x, y; } point; long double distance(point p, point q) { return sqrtl((p.x - q.x) * (p.x - q.x) + (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 sqrtl(s * (s - p) * (s - q) * (s - r)); } typedef struct { long 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(long double* a, long 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; long double theta[200001]; point p[200001]; data d[200001]; scanf("%d", &N); for (i = 1, p[0].x = 0.0, p[0].y = 0.0; i <= N; i++) { scanf("%Lf %Lf", &(p[i].x), &(p[i].y)); theta[i] = atan2l(p[i].y, p[i].x); d[i-1].key = distance(p[0], p[i]); d[i-1].id = i; } merge_sort(N, d); int j; long double ans = 0.0, tmp; for (i = N - 1; i >= 0; i--) { for (j = i - 1; j >= 0; j--) { tmp = d[i].key * d[j].key * 0.5; if (ans >= tmp) break; chmax(&ans, tmp * sinl(fabsl(theta[j] - theta[i]))); } 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; }