B. Cover Points Codeforces Round #511 (Div. 2)【数学】
题目:
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.
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).
Print the minimum length of the shorter side of the triangle. It can be proved that it's always an integer.
3
1 1
1 2
2 1
3
4
1 1
1 2
2 1
2 2
4
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;
}
最新文章
- Struts2.5需要的最少jar文件
- laravel Input Cokkie 的各种方法 超实用!!!
- 公共代码参考(Volley)
- 变形--扭曲 skew()
- 【py网页】urlopen的补充,完美
- C# - Excel - Microsoft Access 数据库引擎找不到对象
- cocos2d-x 3.0rc开发指南:Windows下Android环境搭建
- NEUQ1051: 谭浩强C语言(第三版)习题6.7
- ASP.NET的三层架构(DAL,BLL,UI)
- Chapter 2 Open Book——27
- [转载]【虚拟化系列】VMware vSphere 5.1 网络管理
- 中缀表达式变后缀表达式、后缀表达式(逆波兰)求值(python版本)
- CentOS上PHP完全卸载
- termios结构体的内容
- Squid.conf配置详情
- Omi框架学习之旅 - 生命周期 及原理说明
- 十分钟搞定mac下的phpstorm增加xdebug调试
- php 去除所有空格 包括中文空格圆角空格
- English trip -- Phonics 4 元音字母 i
- dslr control vis usb