这个题和UVa11529很相似。

枚举一个中心点,然后按极角排序,统计以这个点为钝角的三角形的个数,然后用C(n, 3)减去就是答案。

另外遇到直角三角形的情况很是蛋疼,可以用一个eps,不嫌麻烦的话就用整数的向量做点积。

 #include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std; typedef long long LL;
const int maxn = + ;
const double PI = acos(-1.0);
const double eps = 1e-; struct Point
{
double x, y;
Point() {}
Point(double x, double y):x(x), y(y) {}
}p[maxn], p2[maxn]; Point operator - (const Point& A, const Point& B)
{
return Point(A.x-B.x, A.y-B.y);
} double ang[maxn * ]; LL inline C3(int n) { return (LL)n * (n-) / * (n-) / ; } int main()
{
//freopen("in.txt", "r", stdin);
int n, kase = ; while(scanf("%d", &n) == && n)
{
for(int i = ; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y); LL cnt = ;
for(int i = ; i < n; i++)
{
int k = ;
for(int j = ; j < n; j++) if(j != i)
{
p2[k] = p[j] - p[i];
ang[k] = atan2(p2[k].y, p2[k].x);
ang[k + n - ] = ang[k] + PI * 2.0;
k++;
}
k = *n-;
sort(ang, ang + k);
int L, R1 = , R2 = ;
for(L = ; L < n-; L++)
{
double b1 = ang[L] + PI / ;
double b2 = ang[L] + PI;
while(ang[R1] <= b1 - eps) R1++;
while(ang[R2] < b2) R2++;
cnt += R2 - R1;
}
}
LL ans = C3(n) - cnt;
printf("Scenario %d:\nThere are %lld sites for making valid tracks\n", ++kase, ans);
} return ;
}

代码君

最新文章

  1. iptables/Netfilter 学习
  2. Myeclipse的web工程和Eclipse互相转换
  3. Code First is a bad name,这些年我们对Code First的理解都错了 !很震惊吧?
  4. HDU 1085 Holding Bin-Laden Captive --生成函数第一题
  5. this web application instance has been stopped already解决办法
  6. wpf 控件复制 克隆
  7. ArcGIS加载高德、OSM和谷歌等地图
  8. 锅巴视频工作室 ----------------android端蓝牙测试demo--app
  9. Python3 找不到库
  10. go 0000
  11. python0301
  12. linux中安装gcc
  13. MongoVUE 使用教程
  14. ext3文件系统挂载优化--HBase
  15. C# 子类父类方法同名,三种处理方式
  16. 线性回归,感知机,逻辑回归(GD,SGD)
  17. 【LeetCode】64. Minimum Path Sum
  18. LVS初步
  19. handsontable-cell features
  20. 解决无法运行Terminator出现以下问题: File "/usr/bin/terminator"...SyntaxError: invalid syntax

热门文章

  1. JSP | 基础 | 两种方式循环输出
  2. c++语言中类中的静态数据成员为什么必须在类体外初始化?
  3. scikit-learning教程(四)选择合适的估计量
  4. Educational Codeforces Round 24 E
  5. 模拟 2015百度之星资格赛 1003 IP聚合
  6. D. Tavas and Malekas DFS模拟 + kmp + hash || kmp + hash
  7. Android开发-浅谈架构(二)
  8. $(&quot;xxx&quot;).attr添加属性的时候不好用
  9. 46 Simple Python Exercises-Higher order functions and list comprehensions
  10. checkbox设置复选框的只读效果不让用户勾选