TC SRM 585 (一)

DIV 2 1000PT EnclosingTriangleColorful

问有多少个三角形包含了所有的黑色的点

先是两两枚举出所有点对，判断所有的黑点是否在同一侧

然后枚举所有三角形，O(1)判断

预处理O(m*m*n),枚举O(m*m*m)

[cpp]
const int N = 305;
bool upleft[N][N],upright[N][N],downleft[N][N],downright[N][N];
bool updown_toleft[N][N],updown_toright[N][N],leftright_toup[N][N],leftright_todown[N][N];
class EnclosingTriangleColorful {
public:
int xmul(int x0,int y0,int x1,int y1,int x2,int y2){
return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
}
int getNumber(int m, vector x, vector y) {
int n=x.size();
for(int i=1;i for(int j=1;j bool f1=true,f2=true;
for(int k=0;k if(xmul(i,m,0,j,x[k],y[k])<0)
f1=false;
if(xmul(i,m,m,j,x[k],y[k])>0)
f2=false;
}
upleft[i][j]=f1;upright[i][j]=f2;
}
}
for(int i=1;i for(int j=1;j bool f1=true,f2=true;
for(int k=0;k if(xmul(i,0,0,j,x[k],y[k])>0)
f1=false;
if(xmul(i,0,m,j,x[k],y[k])<0)
f2=false;
}
downleft[i][j]=f1;downright[i][j]=f2;
}
}
for(int i=1;i for(int j=1;j bool f1=true,f2=true;
for(int k=0;k if(xmul(i,m,j,0,x[k],y[k])<0)
f1=false;
if(xmul(i,m,j,0,x[k],y[k])>0)
f2=false;
}
updown_toright[i][j]=f1;updown_toleft[i][j]=f2;
}
}
for(int i=1;i for(int j=1;j bool f1=true,f2=true;;
for(int k=0;k if(xmul(0,i,m,j,x[k],y[k])<0)
f1=false;
if(xmul(0,i,m,j,x[k],y[k])>0)
f2=false;
}
leftright_toup[i][j]=f1;leftright_todown[i][j]=f2;
}
}
int ans=0;
for(int i=1;i for(int j=1;j for(int k=1;k if(upleft[i][j]&&upright[i][k]&&leftright_toup[j][k]){
// cout< ans++;
}
}
}
for(int i=1;i for(int j=1;j for(int k=1;k if(updown_toright[i][j]&&upright[i][k]&&downright[j][k]){
// cout< ans++;
}
}
}
for(int i=1;i for(int j=1;j for(int k=1;k if(upleft[i][j]&&updown_toleft[i][k]&&downleft[k][j]){
// cout< ans++;
}
}
}
for(int i=1;i for(int j=1;j for(int k=1;k if(downleft[i][j]&&downright[i][k]&&leftright_todown[j][k]){
// cout< ans++;
}
}
}
return ans;
}


};

const int N = 305;
bool upleft[N][N],upright[N][N],downleft[N][N],downright[N][N];
bool updown_toleft[N][N],updown_toright[N][N],leftright_toup[N][N],leftright_todown[N][N];
class EnclosingTriangleColorful {
public:
int xmul(int x0,int y0,int x1,int y1,int x2,int y2){
return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
}
int getNumber(int m, vector x, vector y) {
int n=x.size();
for(int i=1;i