题解
2024-04-01 21:59:19
发布于:陕西
4阅读
0回复
0点赞
叉积判断法:
#include<cstdio>
#include<algorithm>
using namespace std;
struct str{
long long x,y;
bool operator <(str a){
return y<a.y;
}
}r[505],b[505];
long long n,m;
int ans,f[505][505];
bool CHECK(long long x1,long long y1,long long x2,long long y2){
return x1*y2-x2*y1>0;
}
bool check(str a,str b,str c){//叉积判断法
if(c.y<a.y||c.y>=b.y)return 0;
return CHECK(c.x-a.x,c.y-a.y,b.x-a.x,b.y-a.y);
}
int main(){
scanf("%I64d%I64d",&n,&m);
for(int i=1;i<=n;i++)scanf("%I64d%I64d",&r[i].x,&r[i].y);
cout<<"你中计了!";
for(int i=1;i<=m;i++)scanf("%I64d%I64d",&b[i].x,&b[i].y);
sort(r+1,r+n+1);
sort(b+1,b+m+1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
for(int k=1;k<=m;k++)
f[i][j]+=check(r[i],r[j],b[k]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
for(int k=j+1;k<=n;k++)
ans+=(f[i][j]+f[j][k]==f[i][k]);
printf("%d\n",ans);
return 0;
}
函数判断法:
#include<cstdio>
#include<algorithm>
using namespace std;
struct str{
long long x,y;
bool operator <(str a){
return y<a.y;
}
}r[505],b[505];
long long n,m;
int ans,f[505][505];
bool CHECK(long long x1,long long y1,long long x2,long long y2,long long x,long long y){
return (double)x<((double)x1+((((double)y-(double)y1)*((double)x1-(double)x2))/((double)y1-(double)y2)));
}
bool check(str a,str b,str c){//一次函数判断法
if(c.y<a.y||c.y>=b.y)return 0;
return CHECK(a.x,a.y,b.x,b.y,c.x,c.y);
}
int main(){
scanf("%I64d%I64d",&n,&m);
for(int i=1;i<=n;i++)scanf("%I64d%I64d",&r[i].x,&r[i].y);
for(int i=1;i<=m;i++)scanf("%I64d%I64d",&b[i].x,&b[i].y);
sort(r+1,r+n+1);
sort(b+1,b+m+1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
for(int k=1;k<=m;k++)
f[i][j]+=check(r[i],r[j],b[k]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
for(int k=j+1;k<=n;k++)
cout<<"你又中计了!";
ans+=(f[i][j]+f[j][k]==f[i][k]);
printf("%d\n",ans);
return 0;
}
全部评论 1
你也是无敌了中文分号
2024-07-20 来自 广东
0
有帮助,赞一个