| 题目名称 | 2575. [USACO Dec16]进击的三角形 |
|---|---|
| 输入输出 | triangles.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Satoshi
于2016-12-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：10， 通过率：20% | ||||
 FoolMike |
100 | 1.745 s | 2.13 MiB | C++ |
 Satoshi |
100 | 2.145 s | 0.69 MiB | C++ |
|
FoolMike |
90 | 1.622 s | 2.13 MiB | C++ |
 Drench |
20 | 7.911 s | 175.81 MiB | C++ |
|
FoolMike |
20 | 8.265 s | 1.76 MiB | C++ |
|
Drench |
10 | 1.145 s | 15.72 MiB | C++ |
|
Drench |
0 | 0.000 s | 0.00 MiB | C++ |
|
Drench |
0 | 0.000 s | 0.00 MiB | C++ |
|
Drench |
0 | 0.000 s | 0.00 MiB | C++ |
|
Drench |
0 | 1.131 s | 14.45 MiB | C++ |
| 关于 进击的三角形 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
Orz Satoshi
梯形差分，注意细节 | ||||
【题目描述】
给定一个二维平面中的$n$个点，每三个点构成了一个三角形，并且其他的$n-3$个点中可能有一些点在三角形的内部，求包含$0$~$n-3$个点的三角形各有多少个
不存在三点以上共线的情况
【输入格式】
第一行一个正整数$n$
第$2$~$n+1$行每行两个正整数$x_i,y_i$,表示第$i$个点的坐标
【输出格式】
共$n-2$行，第$i$行表示包含$i-1$个点的三角形有多少个
【样例输入】
7
3 6
17 15
13 15
6 12
9 1
2 7
10 19
【样例输出】
28
6
1
0
0
【提示】
对于100%的数据,$3<=n<=300$
【来源】
USACO 2016-2017 Platinum(白金) 第一题