做法很显然，求出所有的锐角和钝角就能求出有多少个锐角三角形了。
我用了愚钝的方法，写了两三个小时。。。
看了下别人简单的代码。学习了下做法。
sort(temp+1,temp+cnt+1);//排序 For(j,1,cnt)//这一步，复制了一遍所有角，然后就能很好的处理在逆时针的情况 { temp[j+cnt]=temp[j]+2*PI; } int l=1,r=1,le=1; For(j,1,cnt) { while(temp[r]-temp[j]<PI&&r<=2*cnt)r++;//找出<180的角 while(temp[l]-temp[j]<0.5*PI&&l<=2*cnt)l++;//找出<90度的角 while(temp[le]-temp[j]<=eps&&le<=2*cnt)le++;//排除一条直线的情况 ans1=ans1+r-l; ans2=ans2+l-le; }
再附上自己拙略的代码：
// // main.cpp // hdu5784 // // Created by New_Life on 16/8/10. // Copyright © 2016年 chenhuan001. All rights reserved. // #include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; #define PI acos(-1.0) struct point { int x,y; double shita; }g[2020],tg[2020]; int cmp(point p1,point p2) { return p1.shita<p2.shita; } double operator*(point p1, point p2) // 计算叉乘 p1 × p2 { return ((long long)p1.x * p2.y - (long long)p2.x * p1.y); } double operator&(point p1, point p2) { // 计算点积 p1·p2 return ((long long)p1.x * p2.x + (long long)p1.y * p2.y); } int dsub(int p1,int p2) { return (tg[p1]*tg[p2]<=0)&&( (tg[p1]&tg[p2])>0 ); } int savenum[2020]; int main(int argc, const char * argv[]) { int n; while(cin>>n) { for(int i=0;i<n;i++) { scanf("%d%d",&g[i].x,&g[i].y); } long long ans = 0; for(int i=0;i<n;i++) { int cnt = 0; for(int j=0;j<n;j++) { if(j==i) continue; int tx = g[j].x - g[i].x; int ty = g[j].y - g[i].y; tg[cnt].x = tx; tg[cnt].y = ty; tg[cnt++].shita = atan2(ty, tx); } if(cnt < 2) continue; sort(tg,tg+cnt,cmp); memset(savenum,0,sizeof(savenum)); int scnt= cnt; int tcnt = 0; savenum[tcnt++] = 1; for(int j=1;j<cnt;j++) { if( tg[j]*tg[tcnt-1]==0 && ( (tg[j]&tg[tcnt-1])>0 ) ) { savenum[tcnt-1]++; } else { tg[tcnt] = tg[j]; savenum[tcnt] = 1; tcnt++; } } cnt = tcnt; for(int j=0;j<cnt;j++) { ans += savenum[j]*(savenum[j]-1); } if(cnt==1) continue; tcnt = 0; int lf=0,rt=1; while( dsub(0,lf) ){ tcnt += savenum[lf]; lf = (lf-1+cnt)%cnt; if(lf == 0) break; } lf = (lf+1)%cnt; while( rt!=0 && dsub(rt,0) ) tcnt+=savenum[rt],rt = (rt+1)%cnt; //rt = (rt-1+cnt)%cnt; ans += savenum[0]*(tcnt-savenum[0]); ans -= 2*savenum[0]*(scnt-tcnt); for(int j=1;j<cnt;j++) { if(j == lf) { tcnt -= savenum[lf]; lf = (lf+1)%cnt; } if(j == rt) { tcnt += savenum[j]; rt = (rt+1)%cnt; } while( !dsub(j,lf) ) { tcnt -= savenum[lf]; lf= (lf+1)%cnt; //if(lf == j) break; } while(rt!=j && dsub(rt,j) ) tcnt+=savenum[rt],rt=(rt+1)%cnt; ans += savenum[j]*(tcnt-savenum[j]); ans -= 2*savenum[j]*(scnt-tcnt); } } cout<<ans/6<<endl; } return 0; } /* 4 0 0 0 1 1 0 1 1 9 0 0 2 0 0 1 2 1 1 0 1 1 0 2 1 2 2 2 4 0 0 1 1 2 2 3 3 5 0 0 1 1 2 2 -1 0 10000 0 */