http://acm.fzu.edu.cn/problem.php?pid=2242
题意：一个圆上有若干点（不重复），问你可以构成多少锐角三角形。。
思路：排序，枚举每一个点之后二分找到这个点的圆心延长线，之后统计钝角和直角三角形的个数（每次统计向量的左半部分，这样保证不会重复计数）。
排序方法，对于x根据所在象限增加偏移量，可以考虑以x轴划分，上半部分增加一倍偏移量并且-x。。下半部分两倍+x 。注意数组要延长一倍以便于枚举到3，4象限的时候得到正确答案。
坑点：fzoj是I64 。。。黑人问号了好长时间。。
代码：
#include<iostream> #include<stdio.h> #include<algorithm> #define bug(x) cout<<" x "<<x<<endl; using namespace std; const long long maxn=1e5; long long n,r; long long a[50000]; long long x[50000]; char tmp[5]; int main(){ while(scanf("%I64d%I64d",&n,&r)!=EOF){ for(int i=1;i<=n;i++){ scanf("%I64d %s",&x[i],tmp); if(x[i]==r) a[i]=maxn-x[i]; else if(x[i]==-r) a[i]=2*maxn+x[i]; else if(tmp[1]=='>')a[i]=maxn-x[i]; else if(tmp[1]=='<')a[i]=2*maxn+x[i]; } sort(a+1,a+n+1); for(int i=1;i<=n;i++) a[n+i]=a[i]+2*maxn; long long sum=n*(n-1)*(n-2)/6; for(int i=1;i<=n;i++){ long long r=(long long)(upper_bound(a+i,a+n+i+1,a[i]+maxn)-a-1)-i; sum-=r*(r-1)/2; } printf("%I64d\n",sum); } return 0; }