1677--【USACO】Mountain Majesties

1677: 【USACO】Mountain Majesties


时间限制: 1.000 Sec  内存限制: 64 MB
提交: 9  解决: 6
[提交] [状态] [报告] [命题人:]

题目描述

The cows are summering near the Front Range of the Rocky Mountains, not so far from Coach Rob's house. Visible on the horizon are N mountains (N <= 100,000), for example (here, N=5):
                   /\
      /\          /  \  /\
     /  \/\    /\/    \/  \
    /    \ \  /  \    /    \
  -----------------------------
Each mountain is an isosceles triangle whose height is exactly twice the length of its base. A mountain is described by specifying the x-coordinate of each of the two endpoints of its base; these coordinates will be positive integers that fit nicely in a 16-bit signed entity. Your task is to compute the total area of the union of these mountains.

输入

* Line 1: A single integer, N * Lines 2..N+1: Each line describes a single mountain with two sorted space-separated integers.

输出

A single integer, giving the area of the union of the mountains. This area will always be an integer and will always fit into 32 signed bits.

样例

输入  复制
5 2 7 6 9 12 15 14 21 20 25
输出  复制
114

来源/分类