大致题意：
给出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)判断三角形内有无红点。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<time.h>
#include<cstdlib>
#include<cmath>
#include<list>
using namespace std;
#define MAXN 5000006
#define eps 1e-9
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Fore(i,a,b) for(int i=a;i>=b;i--)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mkp make_pair
#define pb push_back
#define cr clear()
#define sz size()
#define met(a,b) memset(a,b,sizeof(a))
#define iossy ios::sync_with_stdio(false)
#define fr freopen
#define pi acos(-1.0)
#define Vector Point
#define fir first
#define sec second
#define it_s_too_hard main
#define I_can_t_solve_it solve
//const long long inf=1LL<<62;
const int inf=1e9+;
const int Mod=1e9+;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
inline int dcmp(ld x){ if(fabs(x)<=eps) return ; return x<?-:;}
inline int scan(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline ll scan(ll x){
int f=;char ch=getchar();x=;
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct Point{
int x,y;
Point(int x=,int y=):x(x),y(y) {}
Point operator - (const Point &a)const { return Point(x-a.x,y-a.y);}
Point operator * (const ll &a)const{return Point(x*a,y*a); }
Point operator + (const Point &a)const{return Point(x+a.x,y+a.y);}
bool operator == (const Point &a)const{ return dcmp(x-a.x)== && dcmp(y-a.y)==;}
bool operator < (const Point &a)const{if(x==a.x) return y<a.y;return x<a.x;}
void read(){scanf("%d%d",&x,&y);}
void out(){cout<<x<<" "<<y<<endl;}
};
double Dot(Vector a,Vector b){
return a.x*b.x+a.y*b.y;
}
double dis(Vector a){
return sqrt(Dot(a,a));
}
ll Cross(Vector a,Vector b){
return a.x*1LL*b.y-a.y*1LL*b.x;
}
bool chk(Point p1,Point p2,Point p3,Point p){
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));
}
int n,m;
Point p[],q[];
int mp[][];
void solve(){
n=scan();m=scan();
met(mp,);
For(i,,n-) p[i].read();
For(i,,m) q[i].read();
sort(p,p+n);
For(i,,n-){
For(j,i+,n-){
if(p[i].x==p[j].x) continue;
For(k,,m){
if(q[k].x>p[i].x && q[k].x<=p[j].x && Cross(q[k]-p[j],p[i]-p[j])<) mp[i][j]++;
}
}
}
int ans=;
For(i,,n-){
For(j,i+,n-){
For(k,j+,n-){
int c1=mp[i][j],c2=mp[j][k],c3=mp[i][k];
if(c1+c2==c3) ans++;
}
}
}
cout<<ans<<endl;
}
int it_s_too_hard(){
int t=;
For(i,,t){
I_can_t_solve_it();
}
return ;
}
蒻菜代码