codeforces 13 D

给你500个红点和蓝点,让你找多少点红点构成的三角形里没有蓝点。

巧妙啊!我们考虑一个很远位置的点,不妨设这个为O,然后n^2枚举红点,考虑Oij里面蓝点的个数,

然后 对于 ijk这个三角形,我们可以求一 OIJ+OJK+OKI,看是否符合条件。

 #include <bits/stdc++.h>
#define p OvO
using namespace std;
typedef long long ll;
int sign(ll k){
if (k>) return ; else if (k<) return -; return ;
}
struct point {
ll x,y;
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
};
ll cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
int clockwise(point k1,point k2,point k3){// k1 k2 k3 逆时针 1 顺时针 -1 否则 0
return sign(cross(k2-k1,k3-k1));
}
int n,m,dp[][];point a[],b[];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%lld%lld",&a[i].x,&a[i].y);
}
for(int i=;i<=m;i++){
scanf("%lld%lld",&b[i].x,&b[i].y);
}
a[] = {,};
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(cross(a[i]-a[],a[j]-a[])<=)continue;
for(int k=;k<=m;k++){
if(clockwise(a[],a[i],b[k])>&&clockwise(a[i],a[j],b[k])>&&clockwise(a[],a[j],b[k])<)
dp[i][j]++;
}
dp[j][i]=-dp[i][j];
}
}
int ans = ;
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
for(int k=j+;k<=n;k++){
if(dp[i][j]+dp[j][k]+dp[k][i]==)
ans++;
}
}
}
printf("%d\n",ans);
}
上一篇:cocos2d-x -------之笔记篇 环境的安装


下一篇:Python面向对象解析