| 题目名称 | 2081. [SYOI 2015] Asm_Def的模拟赛 |
|---|---|
| 输入输出 | trib.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2015-11-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：13， 提交：50， 通过率：26% | ||||
 梦那边的美好ET |
100 | 0.358 s | 3.52 MiB | C++ |
 AAAAAAAAAA |
100 | 0.431 s | 0.68 MiB | C++ |
 Arrow |
100 | 0.601 s | 4.19 MiB | C++ |
 Chenyao2333 |
100 | 0.655 s | 4.19 MiB | C++ |
 Satoshi |
100 | 0.667 s | 0.68 MiB | C++ |
 mikumikumi |
100 | 0.687 s | 0.62 MiB | C++ |
 Shirry |
100 | 0.939 s | 0.66 MiB | C++ |
 devil |
100 | 0.987 s | 0.69 MiB | C++ |
 wire |
100 | 1.201 s | 5.28 MiB | C++ |
 cstdio |
100 | 1.440 s | 0.69 MiB | C++ |
| 本题关联比赛 | |||
| Asm_Def战记之透明计算网络 | |||
| Asm_Def战记之透明计算网络 | |||
| 关于 Asm_Def的模拟赛 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
暴力成功骗到50分
AAAAAAAAAA
2017-08-29 21:41
4楼
| ||||
|
第二个点过不了。。骗分骗过的。。
| ||||
|
造标程的时候觉得后悔出这题了。。。。
| ||||
|
哔了狗了，把题看成求三角形内格点数了……@Satoshi
| ||||
【题目描述】
Asm.Def经过复杂的计算后，切断了合适的线路，使得透明网络计算离线，整个世界开始恢复正常了。但是有些旧的秩序因为不受透明计算网络的控制，变得更加混乱了，比如说NOIP变成了NOI Professional，NOI变成了National Olympiad in Data Structure。为了整治乱象，使得世界秩序恢复正常，Asm.Def决定出一套NOIP模拟赛，让大家看看真的的NOIP难度，重建OI秩序。
Asm.Def出的题如下：现在平面上有n个点，要求你选择其中3个不同点，使得这3个点组成的三角形覆盖平面上的点最多。
可是Asm.Def发现这道NOIP题并不是这么容易，所以为了世界和平，解答这道题的任务交给你了。
【输入格式】
第一行一个整数n，表示平面上有n个点。
接下来n行，每行两个正整数x, y表示在x, y有一个点。
保证所有点不重合
保证不存在三点共线
【输出格式】
输出两行，第一行为选择的三角形最多可以覆盖几个点。
第二行为有多少选择方案使得覆盖的最多。
我们认为存在一个点为第一种方案的三角形某个顶点却不为第二种方案的三角形某个顶点时，这两种方案不同。
【样例输入】
5 2 1 3 3 -1 -1 2 -1 -1 1
【样例输出】
4 2
【提示】
样例解释
如下图，最多覆盖4个点，这是其中一种方案。
（保证不存在3点共线，图中(1,1)点不存在）
另一种方案为选择(-1,1)，(3,3)，(2,-1)为三角形顶点。
数据范围与约定
50%的数据，1 <= n <= 50
100%的数据，1 <= n <= 300, -1000 <= x,y <= 1000
【来源】
Asm_Def战记之透明计算网络