本文主要是介绍Codeforces 849B - Tell Your Worl(思维),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:
给你一堆点,问这些点能不能组成两条平行线,使这两条平行线不重合,而且每条边至少有一个点。
题解:
因为所有点都必须在两条平行线上(如果不在两条平行线上的话,肯定是错的。), 那么我们可以知道,三个点有两个点在一条平行线上,而剩下的一个点单独一条平行线。那么 我们可以用三个点算出三个斜率,第一个点和第二个点的斜率k1,第二个点和第三个点的斜率k2,第一个点和第三个点斜率k3,我们可以得知三个斜率肯定有一个是正确的,那么我们就可以枚举了,
题外话,ORZ,还是太菜了,看了dalao的博客才知道怎么做出来,之前还在死想着怎么暴力,思维这玩意真难锻炼。
#include<stdio.h>
#include<string.h>
#include<math.h>
int y[1005]={0},n;
int check(double k)
{int flag=0,point=-1;for(int i=2;i<=n;i++){if(y[i]-y[1]==k*(i-1)) continue; //同一条直线 flag=1; //有两条不同的直线if(point<0) point=i;else if(y[i]-y[point]!=k*(i-point)) //说明不与第一个点相连的两个点的斜率与第一个点所在的直线的斜率不相同。{flag=0;break;} }if(flag) return 1;else return 0;
}
int main()
{int i;while(~scanf("%d",&n)){memset(y,0,sizeof(y));for(i=1;i<=n;i++)scanf("%d",&y[i]);double k1=1.0*(y[2]-y[1]);//第一个点和第二个点的斜率 double k2=1.0*(y[3]-y[2]);//第三个点和第二个点的斜率 double k3=0.5*(y[3]-y[1]);//第一个点和第三个点的斜率 if(check(k1)||check(k2)||check(k3))printf("Yes\n");elseprintf("No\n");}
}
这篇关于Codeforces 849B - Tell Your Worl(思维)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!