AsiaHatyai-2012 & LA 6142 - Probability Through experiment 逆转思维+二分搜索

AsiaHatyai-2012 & LA 6142 - Probability Through experiment 逆转思维+二分搜索

题意是说在圆上有若干点...问这些点能构成多少个锐角三角形....

很重要的一个突破点...什么时候能够成直角三角形？..当三角形有一条边是该圆直径时此三角形为直角三角形...

所以枚举每个点..用作直径的另一个地方(180度之差的地方)作为分界线..左边一些点...右边一些点...可见..该点与左边任意两点或者右边任意两点构成的三角形必定不是锐角三角形..并且一个非锐角三角形必定会被统计两次...记统计的非锐角三角形个数为sum...那么C(N,3)-sum/2既是锐角三角形的个数...

Program:

//ll long long #define oo 1000000001#define MAXN 20002using namespace std; ll n,sum;double r,p[2*MAXN];ll C(ll n,ll t){ if (t==2) if (n>1) return n*(n-1)/2; else return 0; if (n>2) return n*(n-1)*(n-2)/6; else return 0;}int main(){ // freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int i,t=0,l,r,mid; while (~scanf("%lld%lf",&n,&r)) { if (!n) break; for (i=1;i<=n;i++) scanf("%lf",&p[i]); sort(p+1,p+1+n); for (i=n+1;i<=2*n;i++) p[i]=p[i-n]+360; sum=0; for (i=1;i<=n;i++) { l=0; r=n; while (r-l>1) { mid=(l+r)/2; if (p[i+mid]-p[i]<=180+1e-10) l=mid; else r=mid; } sum+=C(l,2); if (abs(p[i+l]-p[i]-180)<=1e-10) sum+=C(n-l,2); //注意刚好有点落在180度位置的情况 else sum+=C(n-l-1,2); } printf("Case %d: %lld\n",++t,C(n,3)-sum/2); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。