社区讨论
求助:样例没过75分找不到原因
P1153点和线参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lxbkua1o
- 此快照首次捕获于
- 2024/06/12 16:36 2 年前
- 此快照最后确认于
- 2024/06/12 20:29 2 年前
样例没过,4号测试点WA,实在找不到原因了,求助
CPP#include<bits/stdc++.h>
using namespace std;
long long x[11],y[11],a[11],b[11],n=0;
long long ans=0;
bool fun(long long i,long long j)//判断是否相交
{
if(x[b[i%n]]==x[b[i-1]])
{
if(x[b[j]]==x[b[j-1]])
return false;
if(y[b[j]]==y[b[j-1]])
{
if((x[b[j]]-x[b[i-1]])*(x[b[j-1]]-x[b[i-1]])<0 && (y[b[j]]-y[b[i%n]])*(y[b[j-1]]-y[b[i-1]])<0)
return true;
else
return false;
}
double k2,b2;
k2=1.0*(y[b[j]]-y[b[j-1]])/(x[b[j]]-x[b[j-1]]);
b2=y[b[j]]-k2*x[b[j]];
if((x[b[j]]-x[b[i-1]])*(x[b[j-1]]-x[b[i-1]])<0 && (k2*x[b[i-1]]+b2-y[b[i%n]])*(k2*x[b[i-1]]+b2-y[b[i-1]])<0)
return true;
else
return false;
}
if(x[b[j%n]]==x[b[j-1]])
{
if(x[b[i%n]]==x[b[i-1]])
return false;
if(y[b[i%n]]==y[b[i-1]])
{
if(y[b[j]]==y[b[j-1]])
{
if((x[b[j]]-x[b[i%n]])*(x[b[j-1]]-x[b[i-1]])<0 && (y[b[j]]-y[b[i%n]])*(y[b[j-1]]-y[b[i-1]])<0)
return true;
else
return false;
}
}
double k2,b2;
k2=1.0*(y[b[i%n]]-y[b[i-1]])/(x[b[i%n]]-x[b[i-1]]);
b2=y[b[i%n]]-k2*x[b[i%n]];
if((x[b[i%n]]-x[b[j-1]])*(x[b[i-1]]-x[b[j-1]])<0 && (k2*x[b[j-1]]+b2-y[b[j%n]])*(k2*x[b[j-1]]+b2-y[b[j-1]])<0)
return true;
else
return false;
}
if(y[b[i%n]]==y[b[i-1]])
{
if(y[b[j]]==y[b[j-1]])
return false;
if(x[b[j]]==x[b[j-1]])
{
if(y[b[j]]==y[b[j-1]])
{
if((x[b[j]]-x[b[i%n]])*(x[b[j-1]]-x[b[i-1]])<0 && (y[b[j]]-y[b[i%n]])*(y[b[j-1]]-y[b[i-1]])<0)
return true;
else
return false;
}
}
double k2,b2;
k2=1.0*(y[b[j]]-y[b[j-1]])/(x[b[j]]-x[b[j-1]]);
b2=y[b[j]]-k2*x[b[j]];
if((y[b[j]]-y[b[i-1]])*(y[b[j-1]]-y[b[i-1]])<0 && (k2*x[b[i%n]]+b2-y[b[i-1]])*(k2*x[b[i-1]]+b2-y[b[i-1]])<0)
return true;
else
return false;
}
if(y[b[j%n]]==y[b[j-1]])
{
if(y[b[i%n]]==y[b[i-1]])
return false;
if(x[b[i%n]]==x[b[i-1]])
{
if(y[b[j]]==y[b[j-1]])
{
if((x[b[j]]-x[b[i-1]])*(x[b[j-1]]-x[b[i-1]])<0 && (y[b[j]]-y[b[i%n]])*(y[b[j-1]]-y[b[i-1]])<0)
return true;
else
return false;
}
}
double k2,b2;
k2=1.0*(y[b[i%n]]-y[b[i-1]])/(x[b[i%n]]-x[b[i-1]]);
b2=y[b[i%n]]-k2*x[b[i%n]];
if((y[b[i%n]]-y[b[j-1]])*(y[b[i-1]]-y[b[j-1]])<0 && (k2*x[b[j%n]]+b2-y[b[j-1]])*(k2*x[b[j-1]]+b2-y[b[j-1]])<0)
return true;
else
return false;
}
double k1,b1,k2,b2,x0;
k1=1.0*(y[b[i%n]]-y[b[i-1]])/(x[b[i%n]]-x[b[i-1]]);
b1=y[b[i%n]]-k1*x[b[i%n]];
k2=1.0*(y[b[j]]-y[b[j-1]])/(x[b[j]]-x[b[j-1]]);
b2=y[b[j]]-k2*x[b[j]];
if(k1==k2)
return false;
x0=(b2-b1)/(k1-k2);
if((x0-x[b[i-1]])*(x0-x[b[i%n]])<0 && (x0-x[b[j-1]])*(x0-x[b[j]])<0)
return true;
else
return false;
}
void dfs(long long k)
{
if(k==n)
{
long long i,j;
for(i=1;i<=n;i++)//如果存在两条线(i-1点到i点的线与j-1点到j点的线)相交,就break
{
for(j=1;j<i-1;j++)
if(fun(i,j))
break;
if(j<i-1)
break;
}
if(i==n+1)
ans++;
}
else
{
long long i;
for(i=1;i<n;i++)
if(a[i]==0)
{
a[i]=1;
b[k]=i;
dfs(k+1);
a[i]=0;
}
}
}
int main()
{
while(true)
{
cin>>x[n]>>y[n];
if(x[n]==0 && y[n]==0)
break;
n++;
}
n++;
dfs(1);
a[0]=1;
b[0]=0;
cout<<ans/2;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...