历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1671. 三角形——模拟、暴力思路详解，一道大氵题原题链接简单

作者：

Conan15 , 2022-03-21 21:50:55 , 所有人可见 , 阅读 2001

16

2

宣传一下$\Huge\color{green}{春季每日一题题解}$

这题纯暴力，上吧！
暴力

yyds！

这题呢，就是枚举每一个点，看看是否可以构成一个满足条件的三角形。
如果可以构成一个满足条件的三角形的话，那么就计算它的面积乘二，因为题目中说：

由于面积不一定为整数，输出栅栏柱子可以围成的合法三角形的最大面积的两倍。

所以我们用底乘高即可。
判断是否是一个满足条件的三角形，只要满足点i和点j的x坐标相等，点j和点k的y坐标相等。

#include <bits/stdc++.h>
using namespace std;
int n, ans = 0;
pair<int, int> a[110];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].first, &a[i].second);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) {
                if (i == j || i == k || j == k) continue; //重复就continue
                if (a[i].first == a[j].first && a[j].second == a[k].second) {
                    ans = max(ans, abs(a[i].second - a[j].second) * abs(a[i].first - a[k].first));
                    //底乘高取最大值
                    //由于要输出两倍，所以我们这里计算面积不除以二
                }
            }
    printf("%d\n", ans);
    return 0;
}

30 评论

ligg 2022-03-24 20:08

大佬我有个疑问，我把pair函数换成两个数组为什么过不了

Conan15 2022-03-24 20:13

代码发一下吧

ligg 2022-03-24 20:17 回复了 Conan15 的评论

#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]

using namespace std;

const int N=10010;

int n,s;
int x[N],y[N];

int main()
{
scanf(“%d”,&n);
for(int i=1;i<=n;i++)scanf(“%d%d”,&x[i],&y[i]);

int maxs=0;
for(int i=1;i<=n;i++)
{

    for(int j=1;j<=n;j++)
    {

        for(int k=1;k<=n;k++)
        {
            if(i==j||i==k||j==k)continue;
            if(x[j]==x[i]&&y[j]==y[k])
            {
               int l=abs(y[j]-y[i]);
               int h=abs(x[k]-x[j]);

                s=l*h;
            }

             //cout<<s<<endl;

            s=max(s,maxs);

        }
    }
}
cout<<s<<endl;
return 0;

}

ligg 2022-03-24 20:17 回复了 Conan15 的评论

只能过第一个数据

Conan15 2022-03-24 20:20 回复了 ligg 的评论

好的，我看看

Conan15 2022-03-24 21:15 回复了 ligg 的评论

Sorry写作业耽误了下，发现你是最后几行的那个s=max(s, maxs);出问题了~

#include <bits/stdc++.h>
using namespace std;
const int N=110;

int n,s;
int x[N],y[N];

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);

int maxs=0;
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=n;j++)
    {
        for(int k=1;k<=n;k++)
        {
            if(i==j||j==k||i==k)continue;
            int l, h;
            if(x[j]==x[i]&&y[j]==y[k])
            {
                l=y[j]-y[i];
                h=x[k]-x[j];

            }
            s=abs(l*h);
            maxs=max(s,maxs);

        }
    }
}
cout<<maxs<<endl;
return 0;
}

改完了，这个代码可以AC