题目链接: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 ;
}

最新文章

  1. 浅析JS中的模块规范(CommonJS,AMD,CMD)
  2. web网站获取客户端mac地址
  3. TCP/IP协议学习(五) 基于C# Socket的C/S模型
  4. 计算机网络(13)-----java nio手动实现简单的http服务器
  5. 《java中异常和错误》
  6. 用phpcms开发模块时中文乱码问题
  7. php面试题之四——Linux部分(高级部分)
  8. EF——一对一、一对多、多对多关系的配置和级联删除 04(转)
  9. Ubuntu中的.bashrc文件
  10. HTML RGB 颜色表 16进制表 颜色对应表
  11. HDU_4883
  12. c#:实现动态编译,并实现动态MultiProcess功能(来自python multiprocess的想法)
  13. Java关系运算
  14. alias 设置别名
  15. form表单组件
  16. PCIE xilinx v5 IP核使用前的研究
  17. zookeeper集群崩溃处理
  18. 指定nginx某个目录显示目录结构
  19. 《PHP和MySQL Web开发》读书笔记(下篇)
  20. Ubuntu下配置jdk及maven等方法

热门文章

  1. SqlSugar源码学习
  2. 8.JavaScript
  3. 2019牛客暑期多校训练营(第二场)J
  4. Java web 简单的增删改查程序(超详细)
  5. 关于自定义sparkSQL数据源(Hbase)操作中遇到的坑
  6. spark-sql cli 参数 及使用
  7. skb_buff封装
  8. TCP发送窗口更新tcp_ack_update_window
  9. python:BeautifulSoup学习
  10. 【java测试】Junit、Mock+代码覆盖率