• [1204] Chihuo V - More Evidence

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Because Tianyi thought that bury the evidence one by one is too slow, she came up another idea.
    The area is N * N, but because Tianyi has already buried some area, it's not a square now.
    Think of that the left hole is N units width. For each unit of the N width, it stretch to two sides vertically.

    For example, the hole stretches from -1 to 2 at the first unit and the hole stretches from -2 to 3 at the second unit, and it's like the picture below:


    But Tianyi is too lazy to bury all of it, so she find a rectangle to cover it. To cover evidence as more as Tianyi can, she must make the rectangle largest.
    Can you help Tianyi to find a largest rectangle in the hole area? (The rectangle must be put vertically or horizontally and you can't rotate it).


  • 输入
  • This problem has several cases.
    The first line of each case is an integer N (1 <= N <= 100,000), indicates the width of the hole area.
    Next follow N lines, each line has two integers Di and Ui (-10000 <= Di <= 0 <= Ui <= 10000), indicate the vertical stretch of each unit.
  • 输出
  • For each case, you should output the maximum area of the rectangle in the hole area.
  • 样例输入
  • 2
    -1 2
    -2 3
    
  • 样例输出
  • 6
    
  • 提示
  • 来源
  • XadillaX
  • 操作

显示春菜