http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1334. 最远点(梁 盾)
时间限制:2.0s   内存限制:256.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  给你一个N个点的凸多边形,求离每一个点最远的点。
输入格式
  本题有多组数据,第一行一个数T,表示数据组数。
  每组数据第一行一个数N,表示凸多边形点的个数,接下来N对数,依次表示1~N这N个点的坐标,按照逆时针给出。
输出格式
  对于每组数据输出N个数,第i个数表示离第i个点最远的点的编号,如果有多个最远点,输出编号最小的。
样例输入
1
4
0 0
1 0
1 1
0 1
样例输出
3
4
1
2
数据规模和约定
  坐标的绝对值在1e9以内;
  任意点对距离数值的平方不会超过long long;
  令S为每组数据凸多边形点数之和;
  对于20%的数据,S<=2000;
  对于50%的数据,S<=50000;
  对于100%的数据,S<=500000;
  数据有梯度。