大致题意：
给出N个红点和M个蓝点，问可以有多少个红点构成的三角形，其内部不含有蓝点
假设我们现在枚举了一条线段（p[i],p[j]），我们可以记录线段下方满足(min（p[i].x,p[j].x）<x<=max（p[i].x,p[j].x） 的数量
时间复杂度为O（N*N*M）
那么我们就可以枚举三角形O(1)判断三角形内有无红点。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<set> 7 #include<map> 8 #include<stack> 9 #include<time.h> 10 #include<cstdlib> 11 #include<cmath> 12 #include<list> 13 using namespace std; 14 #define MAXN 5000006 15 #define eps 1e-9 16 #define For(i,a,b) for(int i=a;i<=b;i++) 17 #define Fore(i,a,b) for(int i=a;i>=b;i--) 18 #define lson l,mid,rt<<1 19 #define rson mid+1,r,rt<<1|1 20 #define mkp make_pair 21 #define pb push_back 22 #define cr clear() 23 #define sz size() 24 #define met(a,b) memset(a,b,sizeof(a)) 25 #define iossy ios::sync_with_stdio(false) 26 #define fr freopen 27 #define pi acos(-1.0) 28 #define Vector Point 29 #define fir first 30 #define sec second 31 #define it_s_too_hard main 32 #define I_can_t_solve_it solve 33 //const long long inf=1LL<<62; 34 const int inf=1e9+9; 35 const int Mod=1e9+7; 36 typedef unsigned long long ull; 37 typedef long long ll; 38 typedef pair<int,int> pii; 39 typedef pair<ll,ll> pll; 40 typedef double ld; 41 inline int dcmp(ld x){ if(fabs(x)<=eps) return 0; return x<0?-1:1;} 42 inline int scan(){ 43 int x=0,f=1;char ch=getchar(); 44 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 45 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 46 return x*f; 47 } 48 inline ll scan(ll x){ 49 int f=1;char ch=getchar();x=0; 50 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 51 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 52 return x*f; 53 } 54 struct Point{ 55 int x,y; 56 Point(int x=0,int y=0):x(x),y(y) {} 57 Point operator - (const Point &a)const { return Point(x-a.x,y-a.y);} 58 Point operator * (const ll &a)const{return Point(x*a,y*a); } 59 Point operator + (const Point &a)const{return Point(x+a.x,y+a.y);} 60 bool operator == (const Point &a)const{ return dcmp(x-a.x)==0 && dcmp(y-a.y)==0;} 61 bool operator < (const Point &a)const{if(x==a.x) return y<a.y;return x<a.x;} 62 void read(){scanf("%d%d",&x,&y);} 63 void out(){cout<<x<<" "<<y<<endl;} 64 }; 65 double Dot(Vector a,Vector b){ 66 return a.x*b.x+a.y*b.y; 67 } 68 double dis(Vector a){ 69 return sqrt(Dot(a,a)); 70 } 71 ll Cross(Vector a,Vector b){ 72 return a.x*1LL*b.y-a.y*1LL*b.x; 73 } 74 bool chk(Point p1,Point p2,Point p3,Point p){ 75 return abs(Cross(p2-p,p1-p))+abs(Cross(p3-p,p2-p))+abs(Cross(p1-p,p3-p))==abs(Cross(p2-p1,p3-p1)); 76 } 77 int n,m; 78 Point p[5005],q[5005]; 79 int mp[505][505]; 80 void solve(){ 81 n=scan();m=scan(); 82 met(mp,0); 83 For(i,0,n-1) p[i].read(); 84 For(i,1,m) q[i].read(); 85 sort(p,p+n); 86 For(i,0,n-1){ 87 For(j,i+1,n-1){ 88 if(p[i].x==p[j].x) continue; 89 For(k,1,m){ 90 if(q[k].x>p[i].x && q[k].x<=p[j].x && Cross(q[k]-p[j],p[i]-p[j])<0) mp[i][j]++; 91 } 92 } 93 } 94 int ans=0; 95 For(i,0,n-1){ 96 For(j,i+1,n-1){ 97 For(k,j+1,n-1){ 98 int c1=mp[i][j],c2=mp[j][k],c3=mp[i][k]; 99 if(c1+c2==c3) ans++; 100 } 101 } 102 } 103 cout<<ans<<endl; 104 } 105 int it_s_too_hard(){ 106 int t=1; 107 For(i,1,t){ 108 I_can_t_solve_it(); 109 } 110 return 0; 111 }