| 题目名称 | 543. [USACO Open10]数三角形 |
|---|---|
| 输入输出 | tricount.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2011-04-13加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：28， 通过率：42.86% | ||||
 FoolMike |
100 | 0.065 s | 4.87 MiB | C++ |
 cstdio |
100 | 0.074 s | 4.89 MiB | C++ |
 zhengtn03 |
100 | 0.078 s | 2.61 MiB | C++ |
 Chenyao2333 |
100 | 0.081 s | 1.84 MiB | C++ |
 ztx |
100 | 0.082 s | 1.83 MiB | C++ |
 ZXCVBNM_1 |
100 | 0.095 s | 2.60 MiB | C++ |
 ylf123 |
100 | 0.124 s | 4.74 MiB | Pascal |
 Satoshi |
100 | 0.151 s | 3.75 MiB | C++ |
 小DOTA |
100 | 0.226 s | 4.90 MiB | C++ |
 .Xmz |
100 | 0.278 s | 3.32 MiB | C++ |
| 本题关联比赛 | |||
| 20110414 | |||
| 20110414 | |||
| 关于 数三角形 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
数组千万不要开小了！
| ||||
|
又爆long long……药丸呐药丸……
解题报告：http://blog.csdn.net/wmdcstdio/article/details/46745943 | ||||
在一只大灰狼偷偷潜入Farmer Don的牛群被群牛发现后，贝西现在不得不履行着她站岗的职责。
从她的守卫塔向下瞭望简直就是一件烦透了的事情。她决定做一些开发智力的小练习，防止她睡着了。
想象牧场是一个X，Y平面的网格。她将N只奶牛标记为$1…N (1 <= N <= 100,000)$，每只奶牛的坐标为$X_i,Y_i (-100,000 <= X_i <= 100,000;-100,000 <= Y_i <= 100,000; 1 <= i <=N)$。然后她脑海里想象着所有可能由奶牛构成的三角形。如果一个三角形完全包含了原点$(0,0)$，那么她称这个三角形为“黄金三角形”。原点不会落在任何一对奶牛的连线上。另外，不会有奶牛在原点。
给出奶牛的坐标，计算出有多少个“黄金三角形”。
顺便解释一下样例，考虑五只牛，坐标分别为$(-5,0), (0,2), (11,2), (-11,-6), (11,-5)$
下图是由贝西视角所绘出的图示。
............|............
............*..........*.
............|............
-------*----+------------
............|............
............|............
............|............
............|............
............|..........*.
.*..........|............
............|............
所有十个三角形如图下所示：
通过观察，其中有5个构成了“黄金三角形”
輸入格式:
* 第一行:一个整数: $N$
* 第2到第N+1行: 每行两个整数$X_i$，$Y_i$，表示每只牛的坐标
樣例輸入 (文件 tricount.in):
5
-5 0
0 2
11 2
-11 -6
11 -5
輸出格式:
* 第一行: 一行包括一个整数，表示“黄金三角形的数量”
樣例輸出 (文件 tricount.out):
5