Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <sstream>
- #include <iomanip>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <cctype>
- #include <cstring>
- #include <vector>
- #include <list>
- #include <queue>
- #include <deque>
- #include <stack>
- #include <map>
- #include <set>
- #include <algorithm>
- #include <iterator>
- #include <bitset>
- #include <ctime>
- #include <complex>
- using namespace std;
- #define FOR(i,a,b) for (int i = (a); i < (b); i++)
- #define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
- #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
- #define FILL(a,value) memset(a, value, sizeof(a))
- #define SZ(a) (int)a.size()
- #define ALL(a) a.begin(), a.end()
- #define PB push_back
- #define MP make_pair
- typedef long long LL;
- typedef vector<int> VI;
- typedef pair<int, int> PII;
- const double PI = acos(-1.0);
- const int INF = 1000 * 1000 * 1000 + 7;
- const LL LINF = INF * (LL) INF;
- const int MAX = 2000;
- int X[MAX], Y[MAX];
- int P[4][MAX];
- int SZ[4];
- int L[MAX], R[MAX];
- PII V[MAX];
- bool cmp(int i, int j)
- {
- return X[i] * Y[j] - Y[i] * X[j] > 0;
- }
- int len(int id)
- {
- return X[id] * X[id] + Y[id] * Y[id];
- }
- int sq(int i, int j)
- {
- return X[i] * Y[j] - Y[i] * X[j];
- }
- int main()
- {
- //freopen("in.txt", "r", stdin);
- //ios::sync_with_stdio(false); cin.tie(0);
- int n;
- while(scanf("%d", &n) != EOF)
- {
- if (!n)break;
- FOR(i, 0, n)
- {
- scanf("%d%d", X + i, Y + i);
- }
- int mx = 0, mn = INF;
- int mn2 = INF;
- FOR(i, 0, n)
- {
- int x = X[i], y = Y[i];
- FOR(j, 0, n)
- {
- X[j] -= x;
- Y[j] -= y;
- }
- FOR(j, 0, i)
- {
- FOR(k, 0, j)
- {
- int S = X[j] * Y[k] - Y[j] * X[k];
- S = S < 0 ? -S : S;
- mx = S > mx ? S : mx;
- mn = S < mn ? S : mn;
- }
- }
- FOR(q, 0, 4)SZ[q] = 0;
- FOR(j, 0, n)
- {
- if (i == j)continue;
- if (X[j] >= 0 && Y[j] >= 0)P[0][SZ[0]++] = j;
- if (X[j] >= 0 && Y[j] <= 0)P[1][SZ[1]++] = j;
- if (X[j] <= 0 && Y[j] >= 0)P[2][SZ[2]++] = j;
- if (X[j] <= 0 && Y[j] <= 0)P[3][SZ[3]++] = j;
- }
- FOR(q, 0, 4)
- {
- int n = SZ[q];
- sort(P[q], P[q] + n, cmp);
- FOR(i, 0, n)
- {
- L[i] = i-1, R[i] = i+1;
- V[i] = MP(len(P[q][i]), i);
- }
- sort(V, V + n);
- RFOR(i, n, 0)
- {
- int id = V[i].second;
- if (R[id] != n)
- {
- int s = sq(P[q][id], P[q][R[id]]);
- s = s < 0 ? -s : s;
- mn2 = s < mn2 ? s : mn2;
- L[R[id]] = L[id];
- }
- if (L[id] != -1)
- {
- int s = sq(P[q][id], P[q][L[id]]);
- s = s < 0 ? -s : s;
- mn2 = s < mn2 ? s : mn2;
- R[L[id]] = R[id];
- }
- }
- }
- }
- printf("%.1f %.1f\n", mn2 * .5, mx * .5);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement