fork download
copy 
  1. /***********Template Starts Here***********/
  2. #include <bits/stdc++.h>
  3.  
  4. #define pb push_back
  5. #define ff first
  6. #define ss second
  7. #define MP make_pair
  8. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  9. #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
  10. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  11. #define MIN(a,b) ((a)<(b)?(a):(b))
  12. #define MAX(a,b) ((a)>(b)?(a):(b))
  13. #define ALL(x) (x).begin(),(x).end()
  14.  
  15. using namespace std;
  16.  
  17. typedef long long vlong;
  18. typedef pair < int, int > pii;
  19. typedef vector<pii> vii;
  20. typedef vector<int> vi;
  21.  
  22. /***********Template Ends Here***********/
  23.  
  24. vector<pii> p;
  25.  
  26. int main () {
  27.     #ifdef forthright48
  28.     freopen ( "input.txt", "r", stdin );
  29.     //freopen ( "output.txt", "w", stdout );
  30.     #endif // forthright48
  31.  
  32.     int kase;
  33.     scanf ( "%d", &kase );
  34.  
  35.     int cnt = 0;
  36.  
  37.     while ( kase-- ) {
  38.         int l, w;
  39.         scanf ( "%d %d", &l, &w );
  40.  
  41.         int n;
  42.         scanf ( "%d", &n );
  43.  
  44.         p.clear();
  45.  
  46.         vi height; ///Will list all possible heights for top and bottom boundary
  47.  
  48.         FOR(i,0,n-1) {
  49.             int a, b;
  50.             scanf ( "%d %d", &a, &b );
  51.             p.pb ( MP(a,b) ); ///Insert point
  52.             height.pb ( b ); ///Insert possible boundary
  53.         }
  54.  
  55.         height.pb ( 0 ); ///Don't forget the Sand Kingdom Boundaries
  56.         height.pb ( w );
  57.  
  58.         sort ( ALL(height) ); ///Make the heights sorted and unique
  59.         UNIQUE(height);
  60.  
  61.         int m = height.size();
  62.  
  63.         p.pb ( MP(0,0) ); ///Add dummy points to indicate left and right wall of sand kingdom
  64.         p.pb ( MP(l,0) );
  65.  
  66.         n = p.size(); ///Update N
  67.  
  68.         sort ( ALL(p) ); ///Sort all points
  69.  
  70.         vlong res = 0;
  71.  
  72.         FOR(i,0,m-1) { ///Set lower boundary of rectangle
  73.             FOR(j,i+1,m-1) { ///Set upper boundary of rectangle
  74.                 int d = height[i], u = height[j];
  75.  
  76.                 int cur = 0; ///Current point which is acting as left boundary of rectangle
  77.  
  78.                 p[0].ss = d; ///Make sure first and last point, which are Sand Kingdom's wall don't get ignored.
  79.                 p[n-1].ss = d;
  80.  
  81.                 FOR ( k, 1, n - 1 ) {
  82.                     if ( p[k].ss < d || p[k].ss > u ) continue; ///Not inside rectangle
  83.  
  84.                     int width = p[k].ff - p[cur].ff; ///Inside rectangle. Calculate width
  85.  
  86.                     res = MAX(res,width*(u-d)); ///Update result
  87.  
  88.                     if ( p[k].ss > d && p[k].ss < u ) { ///If strictly inside, update left wall.
  89.                         cur = k;
  90.                     }
  91.                 }
  92.             }
  93.         }
  94.  
  95.         printf ("Case %d: %lld\n", ++cnt, res );
  96.  
  97.     }
  98.  
  99.     return 0;
  100. }
  101.  
Time limit exceeded #stdin #stdout 5s 200064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FjvTN2
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!