监视奶牛

柿子饼同学

枚举监视线在XXX, YYY, XYY, YYX 四种情况 , 但是具体代码应该怎么写 , 求教
输入:

6
1 7
0 0
1 2
2 0
1 4
3 4

输出:

1

柿子饼同学

鱼C-小师妹

jhq999

看看

顶级太阳

没看明白题目说的是什么意思。能不能给翻译一下。

柿子饼同学

顶级太阳 发表于 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.

jhq999

给你个证伪的办法，只要有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[px].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[j] = 1; // 打访问标记
            }
        }
        if(linecount > 3){
            cout << 0 << endl;
            return 0;
        }
    }

    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(!vis[i]) cnt++; // 没用过就加
    }
    if(linecount + cnt <= 3) cout << 1 << endl;
    else cout << 0 << endl;
    
    return 0;
}

柿子饼同学

jhq999 发表于 2022-7-9 09:07
给你个证伪的办法，只要有4个点相互不在同一直线的就是伪
例如：
0，0

谢谢回答

额外减小

你好，我是学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[n],y[n],Ax[n]={0},Ay[n]={0},X[n],Y[n];
        for(int count=0;count<n;count++)
        {
                scanf("%d %d",&x[count],&y[count]);
        }
        /*for(int a=0;a<n;a++)
        {
                printf("%d %d\n",x[a],y[a]);
        }*/
        xMax=x[0];
        yMax=y[0];
        xMin=x[0];
        yMin=y[0];
        for(int b=1;b<n;b++)
        {
                xMax=(x[b]>xMax)?x[b]:xMax;
                xMin=(x[b]>xMin)?xMin:x[b];
                yMax=(y[b]>yMax)?y[b]:yMax;
                yMin=(y[b]>yMin)?yMin:y[b];
        }
        bool plane[xMax-xMin+1][yMax-yMin+1]={0};
        for(int c=0;c<n;c++)
        {
                plane[x[c]-xMin][y[c]-yMin]=1;
        }
        for(int d=0;d<xMax-xMin+1;d++)//每个余子式一个循环 
        {
                for(int e=0;e<yMax-yMin+1;e++)
                {
                        bool plane_1[xMax-xMin+1][yMax-yMin+1];
                        for(int f=0;f<xMax-xMin+1;f++)
                        {
                                for(int g=0;g<yMax-yMin+1;g++)
                                {
                                        plane_1[f][g]==plane[f][g];//复制平面 
                                }
                        }
                        for(int i=0;i<yMax-yMin+1;i++)
                        {
                                plane_1[d][i]=0;
                        }
                        for(int j=0;j<xMax-xMin+1;j++)
                        {
                                plane_1[e][j]=0;//求出余子式 
                        }
                        for(int k=0;k<xMax-xMin+1;k++)
                        {
                                for(int l=0;l<yMax-yMin+1;l++)
                                {
                                        if(plane_1[k][l])
                                        {
                                                Ax[z]=k;//返回为点坐标 
                                                Ay[z]=l;
                                                z++;
                                        }
                                }
                        }
                        for(int m=0;m<z;m++)//判断剩余点是否在同一直线 
                        {
                                if(Ax[m]!=Ax[m+1])
                                {
                                        for(int o=0;o<z;o++)
                                        {
                                                if(Ay[o]!=Ay[o+1])
                                                {
                                                        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[count_1]=x[count_1];
                        Y[count_1]=y[count_1];
                        s++;
                        t++;
                }
                else
                {
                        for(u=0;u<s;u++)
                        {
                                if(x[count_1]==X[u])
                                {
                                        break;
                                }
                        }
                        if(u==s)
                        {
                                s++;
                        }
                        
                        for(v=0;v<t;v++)
                        {
                                if(y[count_1]==Y[v])
                                {
                                        break;
                                }
                        }
                        if(v==t)
                        {
                                t++;
                        }
                }
        }
        if((s<=3)||(t<=3))
        {
                flag=1;
        }
        if(flag)
        printf("1\n");
        else
        printf("0\n");
        return 0; 
}

（可能有错，大佬勿喷）

额外减小

额外减小 发表于 2022-7-26 00:52
你好，我是学C的新人，就用C写了个关于你这题的代码，有亿点冗长，不知道对不对，求指教！

（可能有错， ...

我个人认为，C和C++差不多（主观臆断），你可以将就着看看吗？