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

CF 452B 4-point polyline(思维)

4-point polyline

 

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

 

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

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

然后情况主要是分3种:

1.当短边为0的情况:

2.计算dis1

3.计算dis2

4.选出(2)跟(3)中距离之和较大的,输出四个点的顺序。


/*************************************************************************
    > File Name: CF452B.cpp
    > Author: GLSilence
    > Created Time: 2014年07月28日 星期一 18时41分09秒
 ************************************************************************/

#include<stdio.h>
#include<iostream>
using namespace std;

int Distance(int x1, int y1, int x2, int y2){
    return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}

int n, m;
int x1, x2, x3, x4, y1, y2, y3, y4;

int main()
{
    scanf("%d%d", &n, &m);
    bool change = false;
    if(m > n){
        swap(n, m);
        change = true;
    }
    if(m == 0){
        x1 = 1, x2 = n, x3 = 0, x4 = n-1;
        y1 = y2 = y3 = y4 = 0;
    }
    else{
        int dis1 = Distance(0, 0, n, m)*2+Distance(0, 0, n, 0);
        int dis2 = Distance(0, 0, n, m)+Distance(0, 0, n, m-1)*2;

        if(dis1 > dis2){
            x1 = 0, y1 = 0;
            x2 = n, y2 = m;
            x3 = 0, y3 = m;
            x4 = n, y4 = 0;
        }
        else{
            x1 = 0, y1 = 1;
            x2 = n, y2 = m;
            x3 = 0, y3 = 0;
            x4 = n, y4 = m-1;
        }
    }
    if(change){
        swap(x1, y1);
        swap(x2, y2);
        swap(x3, y3);
        swap(x4, y4);
    }
    printf("%d %d\n%d %d\n%d %d\n%d %d\n", x1, y1, x2, y2, x3, y3, x4, y4);


    return 0;
}