| 题目名称 | 1781. [国家集训队2012]最远点 |
|---|---|
| 输入输出 | nt2012_dis.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-10-29加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：17， 提交：67， 通过率：25.37% | ||||
 Flere825 |
100 | 2.027 s | 18.42 MiB | C++ |
 神利·代目 |
100 | 2.545 s | 13.66 MiB | C++ |
 阿狸 |
100 | 2.599 s | 13.67 MiB | C++ |
 assassain |
100 | 2.843 s | 23.18 MiB | C++ |
 FoolMike |
100 | 2.878 s | 23.18 MiB | C++ |
 /k |
100 | 3.058 s | 18.42 MiB | C++ |
 _Horizon |
100 | 3.321 s | 23.20 MiB | C++ |
 0 |
100 | 3.571 s | 25.09 MiB | C++ |
|
0 |
100 | 3.708 s | 23.83 MiB | C++ |
 stone |
100 | 3.794 s | 13.66 MiB | C++ |
| 关于 最远点 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Cooook :
%%%%%%  BaDBoY
2017-08-06 19:36
10楼
| ||||
|
回复 @҉҉ Hzoi_Goodboy :
这个题有K-D树暴力满分QAQ  Cooook
2017-08-06 19:21
9楼
| ||||
|
这个题暴力竟然有35分？？？？不是20%么
BaDBoY
2017-08-06 18:46
8楼
| ||||
|
回复 @溪哥 :
膜拜神犇的分治算法。Orzzzzzzzzzzzzz | ||||
|
回复 @溪哥 :
Orz | ||||
|
回复 @溪哥 :
Orz  zys
2016-04-21 08:15
5楼
| ||||
|
蒟蒻500T留念。。。。。。
| ||||
|
暴力卡过.
| ||||
|
ls+1………………在Tsinsen上卡了一下午+一晚上还是80分……
| ||||
|
我在下面就沒過，怎麼特麼A了（╯‵□′）╯︵┴─┴
| ||||
stdafx.h
Asm.Def
ztx
最远点（梁 盾）
时间限制：0.5s 内存限制：256.0MB
【问题描述】
给你一个N个点的凸多边形，求离每一个点最远的点。
【输入格式】
本题有多组数据，第一行一个数T，表示数据组数。
每组数据第一行一个数N，表示凸多边形点的个数，接下来N对数，依次表示1~N这N个点的坐标，按照逆时针给出。
每组数据第一行一个数N，表示凸多边形点的个数，接下来N对数，依次表示1~N这N个点的坐标，按照逆时针给出。
【输出格式】
对于每组数据输出N个数，第i个数表示离第i个点最远的点的编号，如果有多个最远点，输出编号最小的。
【样例输入】
1
4
0 0
1 0
1 1
0 1
4
0 0
1 0
1 1
0 1
【样例输出】
3
4
1
2
4
1
2
【数据规模和约定】
坐标的绝对值在1e9以内；
任意点对距离数值的平方不会超过long long；
令S为每组数据凸多边形点数之和；
对于20%的数据，S<=2000；
对于50%的数据，S<=50000；
对于100%的数据，S<=500000；
数据有梯度。
任意点对距离数值的平方不会超过long long；
令S为每组数据凸多边形点数之和；
对于20%的数据，S<=2000；
对于50%的数据，S<=50000；
对于100%的数据，S<=500000；
数据有梯度。