题目:

There are nn points on the plane, (x1,y1),(x2,y2),…,(xn,yn)(x1,y1),(x2,y2),…,(xn,yn).

You need to place an isosceles triangle with two sides on the coordinate axis to cover all points (a point is covered if it lies inside the triangle or on the side of the triangle). Calculate the minimum length of the shorter side of the triangle.

Input

First line contains one integer nn (1≤n≤10^5).

Each of the next nn lines contains two integers xixi and yiyi (1≤xi,yi≤10^9).

Output

Print the minimum length of the shorter side of the triangle. It can be proved that it's always an integer.

Examples
input
3
1 1
1 2
2 1
output
3
input
4
1 1
1 2
2 1
2 2
output
4
Note

Illustration for the first example:

Illustration for the second example:

题意分析:

在二维平面坐标系,给你N个坐标点(都在第一象限),让你找一条直线,使这条直线能够与两条坐标轴围成一个等腰三角形,这个三角形能包含所有的点。求这个三角形最短的边长。

边长最短,肯定就是这些点中最外层的点刚好在直线上即可。因为是等腰三角形,所以斜率必然为-1。那么这条直线的表达式为:X+Y= d; 那么所有的点满足X+Y <= d。

这个d的最小值就是我们所要求的,转换一下,相当于就是求输入坐标的x+y的最大值。

代码:

#include <iostream>
#include <cstdio>
using namespace std; int Max(const int a, const int b)
{
return a>b?a:b;
} int main()
{
int N, a, b, ans = 0;
while(~scanf("%d", &N))
{
for(int i = 0; i < N; i++)
{
scanf("%d %d", &a, &b);
ans = Max(ans, a+b);
}
printf("%d\n", ans);
}
return 0;
}

  

最新文章

  1. Struts2.5需要的最少jar文件
  2. laravel Input Cokkie 的各种方法 超实用!!!
  3. 公共代码参考(Volley)
  4. 变形--扭曲 skew()
  5. 【py网页】urlopen的补充,完美
  6. C# - Excel - Microsoft Access 数据库引擎找不到对象
  7. cocos2d-x 3.0rc开发指南:Windows下Android环境搭建
  8. NEUQ1051: 谭浩强C语言(第三版)习题6.7
  9. ASP.NET的三层架构(DAL,BLL,UI)
  10. Chapter 2 Open Book——27
  11. [转载]【虚拟化系列】VMware vSphere 5.1 网络管理
  12. 中缀表达式变后缀表达式、后缀表达式(逆波兰)求值(python版本)
  13. CentOS上PHP完全卸载
  14. termios结构体的内容
  15. Squid.conf配置详情
  16. Omi框架学习之旅 - 生命周期 及原理说明
  17. 十分钟搞定mac下的phpstorm增加xdebug调试
  18. php 去除所有空格 包括中文空格圆角空格
  19. English trip -- Phonics 4 元音字母 i
  20. dslr control vis usb

热门文章

  1. Java AOP 注解配置与xml配置
  2. Luogu 3899 [湖南集训]谈笑风生
  3. CLR VIA C# 泛型的协变和逆变
  4. CodeBlocks调试功能(转)
  5. Linux下ffmpeg安装与开发配置
  6. wpf控件开发基础
  7. ajax data参数
  8. 【C#】is 和 as
  9. 【转】android 布局优化
  10. Snapshot--使用脚本创建快照