Twin Buildings (Problem H, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 1 sec
Memory limit: 256MB
Author: Wiwit Rifai'

# Problem Statement

As you might already know, space has always been a problem in ICPC Jakarta. To cope with this, ICPC Jakarta is planning to build two new buildings. These buildings should have a shape of a rectangle of the same size. Now, their problem is to find land to build the buildings.

There are $N$ lands available for sale. The $i^{\text{th}}$ land has a rectangular shape of size $L_i \times W_i$. For a good feng shui, the building’s side should be parallel to the land’s sides.

One way is to build the two buildings on two different lands, one on each land (not necessarily with the same orientation). A building of size $A \times B$ can be build on the $i^{\text{th}}$ land if and only if at least one of the following is satisfied:

- $A \leq L_i$ and $B \leq W_i$, or
- $A \leq W_i$ and $B \leq L_i$.

Alternatively, it is also possible to build two buildings of $A \times B$ on the $i^{\text{th}}$ land with the same orientation. Formally, it is possible to build two buildings of $A \times B$ on the $i^{\text{th}}$ land if and only if at least one of the following is satisfied:

- $A \times 2 \leq L_i$ and $B \leq W_i$, or
- $A \times 2 \leq W_i$ and $B \leq L_i$, or
- $A \leq L_i$ and $B \times 2 \leq W_i$, or
- $A \leq W_i$ and $B \times 2 \leq L_i$.

Your task in this problem is to help ICPC Jakarta to figure out the largest possible buildings they can build given $N$ available lands. Note that ICPC Jakarta has to build two buildings of $A \times B$; output the largest possible for $A \times B$.

# Input

Input begins with a line containing an integer: $N$ $(1 \leq N \leq 100\,000)$ representing the number of available lands. The next $N$ lines each contains two integers: $L_i\ W_i$ $(1 \leq L_i, W_i \leq 10^9)$ representing the size of the land.

# Output

Output in a line a number representing the largest building that ICPC Jakarta can build with exactly one decimal point (see sample input/output for clarity).

# Sample Input #1
```
2
5 5
3 4
```
# Sample Output #1
```
12.5
```
# Explanation for the sample input/output #1

Two buildings of 2.5 × 5 can be built both on the first land.

# Sample Input #2
```
2
2 5
4 3
```
# Sample Output #2
```
8.0
```
# Explanation for the sample input/output #2

Two buildings of 2 × 4 can be built each on the first and second lands.

# Sample Input #3
```
3
10 1
9 8
7 6
```
# Sample Output #3
```
42.0
```
# Explanation for the sample input/output #3

Two buildings of 7 × 6 can be built each on the second and third lands.


Sample inputs:
2
5 5
3 4

2
2 5
4 3

3
10 1
9 8
7 6

Sample outputs:
12.5

8.0

42.0

# Solution Analysis
Analysis author: Wiwit Rifai'

For each land, we can always build the two buildings on the same land by dividing this land into half horizontally or vertically. So, the answer should be at least half of the largest area of all buildings.

Since the two buildings don’t necessarily have the same orientation if they are on the different lands, then we can assume that we can always swap $L_i$ and $W_i$ for any $i^{\text{th}}$ land. If we place the two building on $i^{\text{th}}$ and $j^{\text{th}}$ land, then the largest building area that we can build is 
$\max(\min(L_i, L_j) \times \min(W_i, W_j), \min(L_i, W_j) \times \min(W_i, L_j))$.

Without loss of generality, we assume that $\min(L_i, W_i, L_j, W_j) = L_i$, then the largest building area that we can build on $i^{\text{th}}$ and $j^{\text{th}}$ land is 
$\max(L_i \times \min(W_i, W_j), L_i \times \min(W_i, \max(W_j, L_j)))$.

To make the solution easier, we can swap $L_i$ and $W_i$ for some lands so that $L_i \leq W_i$ for all buildings.

Let us sort the lands based on the non-increasing $L_i$. Observe that for every $i > j$ we have $L_i \leq L_j$, and then the largest building area that we can build is 
$L_i \times \min(W_i, \max(W_j, L_j)) = L_i \times \min(W_i, W_j)$, since $L_j \leq W_j$. 
So, for any $i$, we just need to find the largest $W_j$ for all $j < i$. We can do all of them in 
$\mathcal{O}(N \log N)$ time-complexity.

**Note**: we must avoid using floating-point numbers since the answer can be very large until $10^{18}$ and it might cause the precision loss.


Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to Judgels format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}