社区讨论

萌新求助,过不了样例啊

P2831[NOIP 2016 提高组] 愤怒的小鸟参与者 3已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@mi866uyo
此快照首次捕获于
2025/11/21 09:16
4 个月前
此快照最后确认于
2025/11/21 09:50
4 个月前
查看原帖
RT,调了好久,不知道哪里手残了
Code:
CPP
#include <bits/stdc++.h>

using namespace std;
const double eps=1e-6;
int n,m;
int T;
double x[25],y[25];
int dp[300005];
int g[20][20];

int main()
{ 
	scanf("%d",&T);
	while(T--)
	{
		memset(g,0,sizeof(g));
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;++i)
		{
			scanf("%lf%lf",&x[i],&y[i]);
		}
		for(int i=0;i<n;++i)
		{
			for(int j=0;j<n;++j)
			{
				if(i==j)
				{				
					continue;
				}
				int a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
				int b=(x[j]*x[j]*y[i]-x[i]*x[i]*y[j])/(x[i]*x[j]*(x[j]-x[i]));
				if(a<=-eps)
				{
					for(int k=0;k<n;++k)
					{
						if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<=eps)
						{
							g[i][j]|=1<<k;
						}
					}
				}
			}
		}
		dp[0]=0;
		int j;
		for(int i=1;i<(1<<n);++i)
		{
			for(j=0;j<n;++j)
			{
				if((1<<j)&i)
				{
					
					break;
				}
			} 
			dp[i]=dp[i^(1<<j)]+1;
			for(int k=0;k<n;++k)
			{
				if(k!=j&&(1<<k)&i)
				{
					dp[i]=(min(dp[i],dp[i^(1<<j)]+1));
				}
			}
		}
		printf("%d\n",dp[(1<<n)-1]);
	}
	return 0;
} 

回复

11 条回复,欢迎继续交流。

正在加载回复...