2019牛客暑期多校训练营(第三场)- H Magic Line (计算几何)
2024-10-21 03:55:04
题目链接:https://ac.nowcoder.com/acm/contest/883/H
题意:给定n个点(n为偶数),求一条直线使得n个点平均分散在直线两端,即每端n/2个点。
思路:把n个点按x升序排列,x相等时按y升序排列,这时候我们取第n/2个点和第n/2+1个点,以它两为界限,把n个点均分。因为n个点的坐标<=1e3,而我们的直线的点可以<=1e9,那么一定可以找到一条很陡的直线满足条件。
图片来自:https://www.cnblogs.com/st1vdy/p/11245932.html
AC代码:
#include<cstdio>
#include<algorithm>
using namespace std; int T,n; struct node{
int x,y;
}pt[]; bool cmp(node a,node b){
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
} int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=;i<=n;++i)
scanf("%d%d",&pt[i].x,&pt[i].y);
sort(pt+,pt+n+,cmp);
int x1=pt[n/].x,y1=pt[n/].y;
int x2=pt[n/+].x,y2=pt[n/+].y;
int xx1,xx2,yy1,yy2;
if((y1+y2)>=)
yy1=1e9,yy2=y1-(yy1-y2);
else
yy2=-*1e9,yy1=y2+(y1-yy2);
if((x1+x2)%==)
xx1=(x1+x2)/-,xx2=xx1+;
else
xx1=x1+(x2-x1)/,xx2=xx1+;
printf("%d %d %d %d\n",xx1,yy1,xx2,yy2);
}
return ;
}
最新文章
- 浅析JS中的模块规范(CommonJS,AMD,CMD)
- web网站获取客户端mac地址
- TCP/IP协议学习(五) 基于C# Socket的C/S模型
- 计算机网络(13)-----java nio手动实现简单的http服务器
- 《java中异常和错误》
- 用phpcms开发模块时中文乱码问题
- php面试题之四——Linux部分(高级部分)
- EF——一对一、一对多、多对多关系的配置和级联删除 04(转)
- Ubuntu中的.bashrc文件
- HTML RGB 颜色表 16进制表 颜色对应表
- HDU_4883
- c#:实现动态编译,并实现动态MultiProcess功能(来自python multiprocess的想法)
- Java关系运算
- alias 设置别名
- form表单组件
- PCIE xilinx v5 IP核使用前的研究
- zookeeper集群崩溃处理
- 指定nginx某个目录显示目录结构
- 《PHP和MySQL Web开发》读书笔记(下篇)
- Ubuntu下配置jdk及maven等方法