AsiaHatyai-2012 & LA 6142 - Probability Through experiment 逆转思维+二分搜索 - c++编程基础

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

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

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

Program:

[cpp]
//https://icpcarchive.ecs.baylor.edu/index.php option=com_onlinejudge&Itemid=8&category=585&page=show_problem&problem=4153
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define oo 1000000001
#define MAXN 20002
using 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;
}