QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#451153#3663. The Biggest TrianglezedanovWA 0ms3732kbC++173.3kb2024-06-22 21:38:272024-06-22 21:38:28

Judging History

你现在查看的是最新测评结果

  • [2024-06-22 21:38:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3732kb
  • [2024-06-22 21:38:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define zedanov                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define int long long
#define el "\n"
const int N = 1e5 + 5, md = 1e9 + 7, inf = 1e9;
double EPS = 1e-9;
// Verify Logic, Check Constrains
// Overflow, Fits in Time/Memory ?

struct point
{
    double x, y;
    double dist(const point &other) const
    {
        double disSq = (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y);
        return sqrt(disSq);
    }
    bool comp(const point &other) const
    {
        return fabs(x - other.x) < EPS && fabs(y - other.y) < EPS;
    }
};
struct Node
{
    point a, b;
    bool comp(const Node &other) const
    {
        auto [c, d] = other;
        double l = (a.y - b.y) * (c.x - d.x);
        double r = (a.x - b.x) * (c.y - d.y);
        return l == r;
    }
    double slope() const
    {
        if (a.y == b.y)
            return 0;
        if (a.x == b.x)
            return inf;
        double ret = (a.y - b.y) / (a.x - b.x);
        return ret;
    }
    point intersect(const Node &other) const
    {
        if (comp(other)) // parallel
            return {-inf, -inf};
        double x = -1, y = -1;
        int hx = 1, hy = 1;
        // vertical line
        if (slope() == inf)
            x = a.x;
        if (other.slope() == inf)
            x = other.a.x, hx = 2;
        // horizontal line
        if (slope() == 0)
            y = a.y;
        if (other.slope() == 0)
            y = other.a.y, hy = 2;

        double c1 = a.y - slope() * a.x;
        double c2 = other.a.y - other.slope() * other.a.x;
        if (x == -1 && y == -1)
        {
            x = (c2 - c1) / (slope() - other.slope());
            y = slope() * x + c1;
        }
        else if (x != -1)
        {
            if (hx == 1)
                y = other.slope() * x + c2;
            else
                y = slope() * x + c1;
        }
        else if (y != -1)
        {
            if (hy == 1)
                x = (y - c2) / other.slope();
            else
                x = (y - c1) / slope();
        }
        else
            assert(false);
        return {x, y};
    }
};
void doWork()
{
    int n;
    cin >> n;
    vector<Node> a(n);
    for (int i = 0; i < n; i++)
    {
        point p1, p2;
        cin >> p1.x >> p1.y >> p2.x >> p2.y;
        a[i].a = p1, a[i].b = p2;
    }
    double ans = -1;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[i].comp(a[j]))
                continue;
            for (int k = k + 1; k < n; k++)
            {
                if (a[i].comp(a[k]) || a[j].comp(a[k]))
                    continue;
                auto p1 = a[i].intersect(a[j]);
                auto p2 = a[i].intersect(a[k]);
                auto p3 = a[j].intersect(a[k]);
                if (p1.comp(p2) || p1.comp(p3) || p2.comp(p3))
                    continue;
                ans = max(ans, p1.dist(p2) + p1.dist(p3) + p2.dist(p3));
            }
        }
    }
    if (ans == -1)
        cout << "no triangle";
    else
        cout << fixed << setprecision(10) << ans;
}

signed main()
{
    zedanov int t = 1;
    // cin >> t;
    while (t--)
        doWork();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3732kb

input:

3
0 0 0 1
0 0 1 0
0 1 1 0

output:

no triangle

result:

wrong answer