三层嵌套循环题解（往下看）

Quartz_Blocks · 2024-04-08 20:02:34 · 题解

P9949 [USACO20FEB] Triangles B 题解

已知 n 个点，求可以合法围成的三角形，并且要有一条轴与 x 轴平行，且有另一条轴与 y轴平行。

由于数据貌似不大，所以我直接使用了暴力。于是就被打了脸（50 分）：

#include <iostream>
using namespace std;
struct node{
    int a,b;
}a[110];
int n,res = 0;
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i].a >> a[i].b;
    for(int i = 1;i <= n-2;i++){
        for(int j = i+1;j <= n-1;j++){
            for(int k = j+1;k <= n;k++){
                if(((a[i].a == a[j].a && a[i].a != a[k].a) || (a[i].a == a[k].a && a[i].a != a[j].a) || (a[j].a == a[k].a && a[i].a != a[j].a)) && ((a[i].b == a[j].b && a[i].b != a[k].b) || (a[i].b == a[k].b && a[i].b != a[j].b) || (a[j].b == a[k].b && a[i].b != a[j].b))){
                    res = max(res,(max(a[i].a,max(a[j].a,a[k].a) - min(a[i].a,min(a[j].a,a[k].a))) * max(a[i].b,max(a[j].b,a[k].b) - min(a[i].b,min(a[j].b,a[k].b)))));
                }
            }
        }
    }
    cout << res;
    return 0;
}

这个代码有很多问题，不能保证数组有序，会有正负数问题。中间码风不够整洁…… 于是有了 90 分代码：

#include <iostream>
#include <algorithm>
using namespace std;
struct node{
    int a,b;
}a[110];
bool cmp(node x,node y){
    if(x.a != y.a) return x.a>y.a;
    return x.b>y.b;
}
int n,res = 0;
int main(){
    cin >> n;
    sort(a+1,a+1+n,cmp);
    for(int i = 1;i <= n;i++) cin >> a[i].a >> a[i].b;
    for(int i = 1;i <= n-2;i++){
        for(int j = i+1;j <= n-1;j++){
            for(int k = j+1;k <= n;k++){
                if(((a[i].a == a[j].a && a[i].a != a[k].a) || (a[i].a == a[k].a && a[i].a != a[j].a) || (a[j].a == a[k].a && a[i].a != a[j].a)) && ((a[i].b == a[j].b && a[i].b != a[k].b) || (a[i].b == a[k].b && a[i].b != a[j].b) || (a[j].b == a[k].b && a[i].b != a[j].b))){
                    int t = int(max(a[i].a,max(a[j].a,a[k].a))-min(a[i].a,min(a[j].a,a[k].a)));
                    int b = int(max(a[i].b,max(a[j].b,a[k].b))-min(a[i].b,min(a[j].b,a[k].b)));
                    res = max(res,t*b/2);
                }
            }
        }
    }
    cout << res*2;
    return 0;
}

问题就出在第 22 行，当 t \times b 得到一个奇数时，t \times b\div2 会由于强制类型转换的原因丢失 0.5，后期再 \times2 时就会少了 ( 0.5 \times 2 ) = 1，导致 WA （悲

于是就有了 AC 代码：

#include <iostream>
#include <algorithm>
using namespace std;
struct node{
    int a,b;
}a[110];
bool cmp(node x,node y){
    if(x.a != y.a) return x.a>y.a;
    return x.b>y.b;
}
int n,res = 0;
int main(){
    cin >> n;
    sort(a+1,a+1+n,cmp);
    for(int i = 1;i <= n;i++) cin >> a[i].a >> a[i].b;
    for(int i = 1;i <= n;i++){
        for(int j = i+1;j <= n;j++){
            for(int k = j+1;k <= n;k++){
                if(((a[i].a == a[j].a && a[i].a != a[k].a) || (a[i].a == a[k].a && a[i].a != a[j].a) || (a[j].a == a[k].a && a[i].a != a[j].a)) && ((a[i].b == a[j].b && a[i].b != a[k].b) || (a[i].b == a[k].b && a[i].b != a[j].b) || (a[j].b == a[k].b && a[i].b != a[j].b))){
                    int t = int(max(a[i].a,max(a[j].a,a[k].a))-min(a[i].a,min(a[j].a,a[k].a)));
                    int b = int(max(a[i].b,max(a[j].b,a[k].b))-min(a[i].b,min(a[j].b,a[k].b)));
                    res = max(res,t*b);
                }
            }
        }
    }
    cout << res;
    return 0;
}