社区讨论

求助:样例没过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 条回复,欢迎继续交流。

正在加载回复...