Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2018
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3. #include <iomanip>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cmath>
  7. #include <cctype>
  8. #include <cstring>
  9. #include <vector>
  10. #include <list>
  11. #include <queue>
  12. #include <deque>
  13. #include <stack>
  14. #include <map>
  15. #include <set>
  16. #include <algorithm>
  17. #include <iterator>
  18. #include <bitset>
  19. #include <ctime>
  20. #include <complex>
  21. using namespace std;
  22.  
  23. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  24. #define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
  25. #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
  26. #define FILL(a,value) memset(a, value, sizeof(a))
  27.  
  28. #define SZ(a) (int)a.size()
  29. #define ALL(a) a.begin(), a.end()
  30. #define PB push_back
  31. #define MP make_pair
  32.  
  33. typedef long long LL;
  34. typedef vector<int> VI;
  35. typedef pair<int, int> PII;
  36.  
  37. const double PI = acos(-1.0);
  38. const int INF = 1000 * 1000 * 1000 + 7;
  39. const LL LINF = INF * (LL) INF;
  40.  
  41. const int MAX = 2000;
  42.  
  43. int X[MAX], Y[MAX];
  44. int P[4][MAX];
  45. int SZ[4];
  46. int L[MAX], R[MAX];
  47. PII V[MAX];
  48.  
  49.  
  50. bool cmp(int i, int j)
  51. {
  52.     return X[i] * Y[j] - Y[i] * X[j] > 0;
  53. }
  54.  
  55. int len(int id)
  56. {
  57.     return X[id] * X[id] + Y[id] * Y[id];
  58. }
  59.  
  60. int sq(int i, int j)
  61. {
  62.     return X[i] * Y[j] - Y[i] * X[j];
  63. }
  64.  
  65. int main()
  66. {
  67.     //freopen("in.txt", "r", stdin);
  68.     //ios::sync_with_stdio(false); cin.tie(0);
  69.    
  70.     int n;
  71.     while(scanf("%d", &n) != EOF)
  72.     {
  73.         if (!n)break;
  74.        
  75.         FOR(i, 0, n)
  76.         {
  77.             scanf("%d%d", X + i, Y + i);
  78.         }
  79.         int mx = 0, mn = INF;
  80.         int mn2 = INF;
  81.        
  82.        
  83.         FOR(i, 0, n)
  84.         {
  85.             int x = X[i], y = Y[i];
  86.             FOR(j, 0, n)
  87.             {
  88.                 X[j] -= x;
  89.                 Y[j] -= y;
  90.             }
  91.            
  92.             FOR(j, 0, i)
  93.             {
  94.                 FOR(k, 0, j)
  95.                 {
  96.                     int S = X[j] * Y[k] - Y[j] * X[k];
  97.                     S = S < 0 ? -S : S;
  98.                     mx = S > mx ? S : mx;
  99.                     mn = S < mn ? S : mn;
  100.                 }
  101.             }
  102.  
  103.             FOR(q, 0, 4)SZ[q] = 0;
  104.            
  105.             FOR(j, 0, n)
  106.             {
  107.                 if (i == j)continue;
  108.                 if (X[j] >= 0 && Y[j] >= 0)P[0][SZ[0]++] = j;
  109.                 if (X[j] >= 0 && Y[j] <= 0)P[1][SZ[1]++] = j;
  110.                 if (X[j] <= 0 && Y[j] >= 0)P[2][SZ[2]++] = j;
  111.                 if (X[j] <= 0 && Y[j] <= 0)P[3][SZ[3]++] = j;
  112.             }
  113.            
  114.             FOR(q, 0, 4)
  115.             {
  116.                 int n = SZ[q];
  117.                 sort(P[q], P[q] + n, cmp);
  118.                 FOR(i, 0, n)
  119.                 {
  120.                     L[i] = i-1, R[i] = i+1;
  121.                     V[i] = MP(len(P[q][i]), i);
  122.                 }
  123.                 sort(V, V + n);
  124.                 RFOR(i, n, 0)
  125.                 {
  126.                     int id = V[i].second;
  127.                     if (R[id] != n)
  128.                     {
  129.                         int s = sq(P[q][id], P[q][R[id]]);
  130.                         s = s < 0 ? -s : s;
  131.                         mn2 = s < mn2 ? s : mn2;
  132.                         L[R[id]] = L[id];
  133.                     }
  134.                     if (L[id] != -1)
  135.                     {
  136.                         int s = sq(P[q][id], P[q][L[id]]);
  137.                         s = s < 0 ? -s : s;
  138.                         mn2 = s < mn2 ? s : mn2;
  139.                         R[L[id]] = R[id];
  140.                     }
  141.                 }
  142.             }
  143.            
  144.            
  145.         }
  146.        
  147.         printf("%.1f %.1f\n", mn2 * .5, mx * .5);
  148.        
  149.        
  150.     }
  151.    
  152.    
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement