首页 > 代码库 > bzoj 1914: [Usaco2010 OPen]Triangle Counting 数三角形 容斥
bzoj 1914: [Usaco2010 OPen]Triangle Counting 数三角形 容斥
1914: [Usaco2010 OPen]Triangle Counting 数三角形
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 272 Solved: 143
[Submit][Status]
Description
在一只大灰狼偷偷潜入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)。下图是由贝西视角所绘出的图示。
Input
第一行:一个整数: N第2到第N+1行: 每行两个整数X_i，Y_i，表示每只牛的坐标
Output
* 第一行: 一行包括一个整数，表示“黄金三角形的数量”
Sample Input
5
-5 0
0 2
11 2
-11 -6
11 -5
-5 0
0 2
11 2
-11 -6
11 -5
Sample Output
5
HINT
Source
Gold
这道题容易出问题的地方一点就是由于有一步整体乘2导致数组开小了，另一点是关于三点共线，这个问题想了很久结果发现其实容斥中已经自动排除掉这种情况了。另外顺便提一下，atan(x) -> [-pi/2,pi/2)
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define MAXN 200010#define inf 1e1000#define PI 3.1415926535897832const double pi=PI;double h[MAXN];int main(){ freopen("input.txt","r",stdin); int i,j,k; int n,x,y; scanf("%d",&n); for (i=0;i<n;i++) { scanf("%d%d",&x,&y); double a; if (x)a=(double)y/x; else if (x>0)a=(double)inf; else a=-inf; h[i]=atan(a); if (x<0 || (x==0 && y>0))h[i]+=PI; h[i+n]=h[i]+PI*2; } long long ans=(long long)n*(n-1)*(n-2)/6; n*=2; sort(h,h+n); for (i=0;i*2<n;i++) { x=upper_bound(h+i,h+n,h[i]+PI)-h-i;; x--; ans-=(long long)x*(x-1)/2; } printf("%lld\n",ans); return 0;}
bzoj 1914: [Usaco2010 OPen]Triangle Counting 数三角形 容斥
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。