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 <int> x, vector <int> y) {
int n=x.size();
for(int i=1;i<m;i++){
for(int j=1;j<m;j++){
bool f1=true,f2=true;
for(int k=0;k<n;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<m;i++){
for(int j=1;j<m;j++){
bool f1=true,f2=true;
for(int k=0;k<n;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<m;i++){
for(int j=1;j<m;j++){
bool f1=true,f2=true;
for(int k=0;k<n;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<m;i++){
for(int j=1;j<m;j++){
bool f1=true,f2=true;;
for(int k=0;k<n;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<m;i++) //up
for(int j=1;j<m;j++){ //left
for(int k=1;k<m;k++){ //right
if(upleft[i][j]&&upright[i][k]&&leftright_toup[j][k]){
// cout<<i<<" "<<j<<" "<<k<<" "<<leftright[j][k]<<endl;
ans++;
}
}
}
for(int i=1;i<m;i++) //up
for(int j=1;j<m;j++){ //down
for(int k=1;k<m;k++){ //right
if(updown_toright[i][j]&&upright[i][k]&&downright[j][k]){
// cout<<i<<" "<<j<<" "<<k<<endl;
ans++;
}
}
}
for(int i=1;i<m;i++) //up
for(int j=1;j<m;j++){ //left
&n
补充：软件开发 , C++ ,
