监视奶牛

柿子饼同学

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

1. 
   
2. 6
   
3. 1 7
   
4. 0 0
   
5. 1 2
   
6. 2 0
   
7. 1 4
   
8. 3 4

复制代码

输出:

1. 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 四种情况是什么意思。
光看题目本身，应该不太难。

根据您的思路写的代码 , 但是跑不对 , 求指教

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, px, py, linecount = 0;
   
5. map<int, bool> vis;
   
6. map<int, vector<int> > mpx; // x 相同的就记下点的号码
   
7. 
   
8. int main(){
   
9.     ios::sync_with_stdio(0);
   
10.     cin.tie(0); cout.tie(0);
    
11.    
    
12.     cin >> n;
    
13.     for(int i = 0; i < n; i++){
    
14.         cin >> px >> py;
    
15.         mpx[px].push_back(i); // 用 i 作为每个点的号
    
16.     }
    
17. 
    
18.     for(auto i = mpx.begin(); i != mpx.end(); i++){
    
19.         if(i->second.size() > 1){
    
20.             linecount++;
    
21.             for(auto j : i->second){
    
22.                 vis[j] = 1; // 打访问标记
    
23.             }
    
24.         }
    
25.         if(linecount > 3){
    
26.             cout << 0 << endl;
    
27.             return 0;
    
28.         }
    
29.     }
    
30. 
    
31.     int cnt = 0;
    
32.     for(int i = 0; i < n; i++){
    
33.         if(!vis[i]) cnt++; // 没用过就加
    
34.     }
    
35.     if(linecount + cnt <= 3) cout << 1 << endl;
    
36.     else cout << 0 << endl;
    
37.    
    
38.     return 0;
    
39. }
    

复制代码

柿子饼同学

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

谢谢回答

额外减小

你好，我是学C的新人，就用C写了个关于你这题的代码，有亿点冗长，不知道对不对，求指教！

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         printf("请输入牛的数量：");
   
6.         int n,xMax,xMin,yMax,yMin,count_x=0,count_y=0,z=0,p=0,s=0,t=0,u,v;
   
7.        
   
8.         bool flag=0;
   
9.         scanf("%d",&n);
   
10.         printf("请输入每头牛的坐标（每行1组，用空格隔开）：\n");
    
11.         int x[n],y[n],Ax[n]={0},Ay[n]={0},X[n],Y[n];
    
12.         for(int count=0;count<n;count++)
    
13.         {
    
14.                 scanf("%d %d",&x[count],&y[count]);
    
15.         }
    
16.         /*for(int a=0;a<n;a++)
    
17.         {
    
18.                 printf("%d %d\n",x[a],y[a]);
    
19.         }*/
    
20.         xMax=x[0];
    
21.         yMax=y[0];
    
22.         xMin=x[0];
    
23.         yMin=y[0];
    
24.         for(int b=1;b<n;b++)
    
25.         {
    
26.                 xMax=(x[b]>xMax)?x[b]:xMax;
    
27.                 xMin=(x[b]>xMin)?xMin:x[b];
    
28.                 yMax=(y[b]>yMax)?y[b]:yMax;
    
29.                 yMin=(y[b]>yMin)?yMin:y[b];
    
30.         }
    
31.         bool plane[xMax-xMin+1][yMax-yMin+1]={0};
    
32.         for(int c=0;c<n;c++)
    
33.         {
    
34.                 plane[x[c]-xMin][y[c]-yMin]=1;
    
35.         }
    
36.         for(int d=0;d<xMax-xMin+1;d++)//每个余子式一个循环
    
37.         {
    
38.                 for(int e=0;e<yMax-yMin+1;e++)
    
39.                 {
    
40.                         bool plane_1[xMax-xMin+1][yMax-yMin+1];
    
41.                         for(int f=0;f<xMax-xMin+1;f++)
    
42.                         {
    
43.                                 for(int g=0;g<yMax-yMin+1;g++)
    
44.                                 {
    
45.                                         plane_1[f][g]==plane[f][g];//复制平面
    
46.                                 }
    
47.                         }
    
48.                         for(int i=0;i<yMax-yMin+1;i++)
    
49.                         {
    
50.                                 plane_1[d][i]=0;
    
51.                         }
    
52.                         for(int j=0;j<xMax-xMin+1;j++)
    
53.                         {
    
54.                                 plane_1[e][j]=0;//求出余子式
    
55.                         }
    
56.                         for(int k=0;k<xMax-xMin+1;k++)
    
57.                         {
    
58.                                 for(int l=0;l<yMax-yMin+1;l++)
    
59.                                 {
    
60.                                         if(plane_1[k][l])
    
61.                                         {
    
62.                                                 Ax[z]=k;//返回为点坐标
    
63.                                                 Ay[z]=l;
    
64.                                                 z++;
    
65.                                         }
    
66.                                 }
    
67.                         }
    
68.                         for(int m=0;m<z;m++)//判断剩余点是否在同一直线
    
69.                         {
    
70.                                 if(Ax[m]!=Ax[m+1])
    
71.                                 {
    
72.                                         for(int o=0;o<z;o++)
    
73.                                         {
    
74.                                                 if(Ay[o]!=Ay[o+1])
    
75.                                                 {
    
76.                                                         p++;
    
77.                                                 }
    
78.                                         }
    
79.                                 }
    
80.                         }
    
81.                         if(p==z)
    
82.                         {
    
83.                                 continue;
    
84.                         }
    
85.                         else
    
86.                         {
    
87.                                 flag=1;
    
88.                         }
    
89.                 }
    
90.                 if(flag)
    
91.                 {       
    
92.                         break;
    
93.                 }
    
94.         }
    
95.         //case 3/4
    
96.         for(int count_1=0;count_1<n;count_1++)
    
97.         {
    
98.                 if(!count_1)
    
99.                 {
    
100.                         X[count_1]=x[count_1];
     
101.                         Y[count_1]=y[count_1];
     
102.                         s++;
     
103.                         t++;
     
104.                 }
     
105.                 else
     
106.                 {
     
107.                         for(u=0;u<s;u++)
     
108.                         {
     
109.                                 if(x[count_1]==X[u])
     
110.                                 {
     
111.                                         break;
     
112.                                 }
     
113.                         }
     
114.                         if(u==s)
     
115.                         {
     
116.                                 s++;
     
117.                         }
     
118.                        
     
119.                         for(v=0;v<t;v++)
     
120.                         {
     
121.                                 if(y[count_1]==Y[v])
     
122.                                 {
     
123.                                         break;
     
124.                                 }
     
125.                         }
     
126.                         if(v==t)
     
127.                         {
     
128.                                 t++;
     
129.                         }
     
130.                 }
     
131.         }
     
132.         if((s<=3)||(t<=3))
     
133.         {
     
134.                 flag=1;
     
135.         }
     
136.         if(flag)
     
137.         printf("1\n");
     
138.         else
     
139.         printf("0\n");
     
140.         return 0;
     
141. }

复制代码

（可能有错，大佬勿喷）

额外减小

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

（可能有错， ...

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