題意是說在圓上有若干點...問這些點能構成多少個銳角三角形....
很重要的一個突破點...什麼時候能夠成直角三角形？..當三角形有一條邊是該圓直徑時此三角形為直角三角形...
所以枚舉每個點..用作直徑的另一個地方(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<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#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;
}
