ural 1245. Pictures

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <iostream>
  9 #include <algorithm>
 10 #include <map>
 11 #include <set>
 12 #include <ctime>
 13 #include <iomanip>
 14 using namespace std;
 15 typedef long long LL;
 16 typedef double DB;
 17 #define For(i, s, t) for(int i = (s); i <= (t); i++)
 18 #define Ford(i, s, t) for(int i = (s); i >= (t); i--)
 19 #define Rep(i, t) for(int i = (0); i < (t); i++)
 20 #define Repn(i, t) for(int i = ((t)-1); i >= (0); i--)
 21 #define rep(i, x, t) for(int i = (x); i < (t); i++)
 22 #define MIT (2147483647)
 23 #define INF (1000000001)
 24 #define MLL (1000000000000000001LL)
 25 #define sz(x) ((int) (x).size())
 26 #define clr(x, y) memset(x, y, sizeof(x))
 27 #define puf push_front
 28 #define pub push_back
 29 #define pof pop_front
 30 #define pob pop_back
 31 #define ft first
 32 #define sd second
 33 #define mk make_pair
 34 inline void SetIO(string Name)
 35 {
 36     string Input = Name+".in",
 37     Output = Name+".out";
 38     freopen(Input.c_str(), "r", stdin),
 39     freopen(Output.c_str(), "w", stdout);
 40 }
 41 
 42 inline int Getint()
 43 {
 44     int Ret = 0;
 45     char Ch = ‘ ‘;
 46     bool Flag = 0;
 47     while(!(Ch >= ‘0‘ && Ch <= ‘9‘))
 48     {
 49         if(Ch == ‘-‘) Flag ^= 1;
 50         Ch = getchar();
 51     }
 52     while(Ch >= ‘0‘ && Ch <= ‘9‘)
 53     {
 54         Ret = Ret * 10 + Ch - ‘0‘;
 55         Ch = getchar();
 56     }
 57     return Flag ? -Ret : Ret;
 58 }
 59 
 60 const int N = 1010, M = 100;
 61 struct Point
 62 {
 63     int x, y, r;
 64     
 65     inline void Read()
 66     {
 67         r = Getint();
 68         x = Getint();
 69         y = Getint();
 70     }
 71     
 72     inline bool operator <(const Point &A) const
 73     {
 74         return x < A.x;
 75     }
 76 } Arr[N];
 77 int n;
 78 int LU[N], LD[N], RU[N], RD[N], Left[N], Right[N];
 79 int Ans = MIT;
 80 
 81 inline void Input() 
 82 {
 83     n = Getint();
 84     For(i, 1, n) Arr[i].Read();
 85 }
 86 
 87 inline void Work()
 88 {
 89     sort(Arr + 1, Arr + 1 + n);
 90     Right[0] = -INF, LD[0] = INF, LU[0] = -INF;
 91     For(i, 1, n)
 92     {
 93         Right[i] = max(Right[i - 1], Arr[i].x + Arr[i].r);
 94         LU[i] = max(LU[i - 1], Arr[i].y + Arr[i].r);
 95         LD[i] = min(LD[i - 1], Arr[i].y - Arr[i].r);
 96     }
 97     Left[n + 1] = INF, RD[n + 1] = INF, RU[n + 1] = -INF;
 98     Ford(i, n, 1)
 99     {
100         Left[i] = min(Left[i + 1], Arr[i].x - Arr[i].r);
101         RU[i] = max(RU[i + 1], Arr[i].y + Arr[i].r);
102         RD[i] = min(RD[i + 1], Arr[i].y - Arr[i].r);
103     }
104     
105     For(i, 2, n)
106         if(Right[i - 1] <= Left[i])
107             Ans = min(Ans, 
108             max(M, Right[i - 1] - Left[1]) * max(M, LU[i - 1] - LD[i - 1]) +
109             max(M, Right[n] - Left[i]) * max(M, RU[i] - RD[i]));
110 }
111 
112 inline void Solve()
113 {
114     Work();
115     For(i, 1, n) swap(Arr[i].x, Arr[i].y);
116     Work();
117     
118     Ans = min(Ans, max(M, Right[n] - Left[1]) * max(M, LU[n] - LD[n]));
119     
120     printf("%d\n", Ans);
121 }
122 
123 int main()
124 {
125     #ifndef ONLINE_JUDGE 
126     SetIO("D");
127     #endif 
128     Input();
129     Solve();
130     return 0;
131 }