监视奶牛
枚举监视线在XXX, YYY, XYY, YYX 四种情况 , 但是具体代码应该怎么写 , 求教输入:
6
1 7
0 0
1 2
2 0
1 4
3 4
输出:1 本帖最后由 柿子饼同学 于 2022-7-8 10:37 编辑
{:10_266:}
{:10_245:} 本帖最后由 jhq999 于 2022-7-8 15:31 编辑
看看 没看明白题目说的是什么意思。能不能给翻译一下。 顶级太阳 发表于 2022-7-8 15:45
没看明白题目说的是什么意思。能不能给翻译一下。
就是在一个平面里， 给出所有牛的坐标
现在有三个线 ，可以垂直也可以平行于 x 轴
问能否用这三根线串起所有的牛 不太理解你描述的 XXX、YYY、XYY、YYX 四种情况是什么意思。
光看题目本身，应该不太难。
我的思路：
坐标 (x, y) x行y列
任选一个方向轴（x或y），给所有坐标的不同数值计算一个权值 n，选择 x轴就计算 x的坐标，选择 y轴则计算 y坐标
以选择 x轴，输入数据同楼主输入为例：1的权值为 3，0的权值为 1，2的权值为 1，3的权值为 1。
从权值n>1的数值中，由大到小放线。（可设跳出条件：三条线已用完）
故在y=1放线，此时剩余两条线，且 x轴方向不再有权值n>1的坐标
进入下一阶段
遍历剩余坐标的 y值，计算 y的不同值个数，此例中剩余 y值有 0|4 两个，将该个数与剩余 线 的条数进行对比，满足小于等于条件，即可成功，返回 1；反之 返回 0. 给你个证伪的办法，只要有4个点相互不在同一直线的就是伪
例如：
0，0
1，3
2，1
4，5 风车呼呼呼 发表于 2022-7-8 20:38
不太理解你描述的 XXX、YYY、XYY、YYX 四种情况是什么意思。
光看题目本身，应该不太难。
根据您的思路写的代码 , 但是跑不对 , 求指教#include <bits/stdc++.h>
using namespace std;
int n, px, py, linecount = 0;
map<int, bool> vis;
map<int, vector<int> > mpx; // x 相同的就记下点的号码
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0; i < n; i++){
cin >> px >> py;
mpx.push_back(i); // 用 i 作为每个点的号
}
for(auto i = mpx.begin(); i != mpx.end(); i++){
if(i->second.size() > 1){
linecount++;
for(auto j : i->second){
vis = 1; // 打访问标记
}
}
if(linecount > 3){
cout << 0 << endl;
return 0;
}
}
int cnt = 0;
for(int i = 0; i < n; i++){
if(!vis) cnt++; // 没用过就加
}
if(linecount + cnt <= 3) cout << 1 << endl;
else cout << 0 << endl;
return 0;
}
jhq999 发表于 2022-7-9 09:07
给你个证伪的办法，只要有4个点相互不在同一直线的就是伪
例如：
0，0
谢谢回答{:10_254:} 你好，我是学C的新人，就用C写了个关于你这题的代码，有亿点冗长，不知道对不对，求指教！
#include <stdio.h>
int main()
{
printf("请输入牛的数量：");
int n,xMax,xMin,yMax,yMin,count_x=0,count_y=0,z=0,p=0,s=0,t=0,u,v;
bool flag=0;
scanf("%d",&n);
printf("请输入每头牛的坐标（每行1组，用空格隔开）：\n");
int x,y,Ax={0},Ay={0},X,Y;
for(int count=0;count<n;count++)
{
scanf("%d %d",&x,&y);
}
/*for(int a=0;a<n;a++)
{
printf("%d %d\n",x,y);
}*/
xMax=x;
yMax=y;
xMin=x;
yMin=y;
for(int b=1;b<n;b++)
{
xMax=(x>xMax)?x:xMax;
xMin=(x>xMin)?xMin:x;
yMax=(y>yMax)?y:yMax;
yMin=(y>yMin)?yMin:y;
}
bool plane={0};
for(int c=0;c<n;c++)
{
plane-xMin]-yMin]=1;
}
for(int d=0;d<xMax-xMin+1;d++)//每个余子式一个循环
{
for(int e=0;e<yMax-yMin+1;e++)
{
bool plane_1;
for(int f=0;f<xMax-xMin+1;f++)
{
for(int g=0;g<yMax-yMin+1;g++)
{
plane_1==plane;//复制平面
}
}
for(int i=0;i<yMax-yMin+1;i++)
{
plane_1=0;
}
for(int j=0;j<xMax-xMin+1;j++)
{
plane_1=0;//求出余子式
}
for(int k=0;k<xMax-xMin+1;k++)
{
for(int l=0;l<yMax-yMin+1;l++)
{
if(plane_1)
{
Ax=k;//返回为点坐标
Ay=l;
z++;
}
}
}
for(int m=0;m<z;m++)//判断剩余点是否在同一直线
{
if(Ax!=Ax)
{
for(int o=0;o<z;o++)
{
if(Ay!=Ay)
{
p++;
}
}
}
}
if(p==z)
{
continue;
}
else
{
flag=1;
}
}
if(flag)
{
break;
}
}
//case 3/4
for(int count_1=0;count_1<n;count_1++)
{
if(!count_1)
{
X=x;
Y=y;
s++;
t++;
}
else
{
for(u=0;u<s;u++)
{
if(x==X)
{
break;
}
}
if(u==s)
{
s++;
}
for(v=0;v<t;v++)
{
if(y==Y)
{
break;
}
}
if(v==t)
{
t++;
}
}
}
if((s<=3)||(t<=3))
{
flag=1;
}
if(flag)
printf("1\n");
else
printf("0\n");
return 0;
}
（可能有错，大佬勿喷）{:10_254:} 额外减小 发表于 2022-7-26 00:52
你好，我是学C的新人，就用C写了个关于你这题的代码，有亿点冗长，不知道对不对，求指教！
（可能有错， ...
我个人认为，C和C++差不多（主观臆断），你可以将就着看看吗？
页:
[1]