首页 > 代码库 > CF 452B 4-point polyline(思维)

CF 452B 4-point polyline(思维)

2024-07-14 12:13:45   223人阅读

4-point polyline

 

大意：给你一个网格，从(0, 0)到(n, m)。在网格中选出4个不相同的点，按序相连成3段，求3段想加之和最长的情况是什么，输出这种情况。

 

思路：当时做的时候各种蛋疼，主要是没想对方向，导致一直WA在第3组。今天看到了一个比较清晰的思路。

首先，确定一个短边，我取了m为较短边。

然后情况主要是分3种:

1.当短边为0的情况：

2.计算dis1

 

3.计算dis2

4.选出（2）跟（3）中距离之和较大的，输出四个点的顺序。

 

 1 /************************************************************************* 2     > File Name: CF452B.cpp 3     > Author: GLSilence 4     > Created Time: 2014年07月28日 星期一 18时41分09秒 5  ************************************************************************/ 6  7 #include<stdio.h> 8 #include<iostream> 9 using namespace std;10 11 int Distance(int x1, int y1, int x2, int y2){12     return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);13 }14 15 int n, m;16 int x1, x2, x3, x4, y1, y2, y3, y4;17 18 int main()19 {20     scanf("%d%d", &n, &m);21     bool change = false;22     if(m > n){23         swap(n, m);24         change = true;25     }26     if(m == 0){27         x1 = 1, x2 = n, x3 = 0, x4 = n-1;28         y1 = y2 = y3 = y4 = 0;29     }30     else{31         int dis1 = Distance(0, 0, n, m)*2+Distance(0, 0, n, 0);32         int dis2 = Distance(0, 0, n, m)+Distance(0, 0, n, m-1)*2;33 34         if(dis1 > dis2){35             x1 = 0, y1 = 0;36             x2 = n, y2 = m;37             x3 = 0, y3 = m;38             x4 = n, y4 = 0;39         }40         else{41             x1 = 0, y1 = 1;42             x2 = n, y2 = m;43             x3 = 0, y3 = 0;44             x4 = n, y4 = m-1;45         }46     }47     if(change){48         swap(x1, y1);49         swap(x2, y2);50         swap(x3, y3);51         swap(x4, y4);52     }53     printf("%d %d\n%d %d\n%d %d\n%d %d\n", x1, y1, x2, y2, x3, y3, x4, y4);54 55 56     return 0;57 }
CF 452B

 


联系
我们