QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373174#3663. The Biggest TriangleMahmoudBassemWA 1ms3812kbC++204.6kb2024-04-01 05:29:312024-04-01 05:29:33

Judging History

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

  • [2024-04-01 05:29:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3812kb
  • [2024-04-01 05:29:31]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define el '\n'
#define fi first
#define se second

#define Nine_seconds ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ld long double
const ld EPS = 1e-9;

struct point {
    ld x{}, y{};

    point() = default;

    point(ld x, ld y) : x(x), y(y) {}

    point &operator+=(const point &t) {
        x += t.x;
        y += t.y;
        return *this;
    }

    point &operator-=(const point &t) {
        x -= t.x;
        y -= t.y;
        return *this;
    }

    point &operator*=(ld t) {
        x *= t;
        y *= t;
        return *this;
    }

    point &operator/=(ld t) {
        x /= t;
        y /= t;
        return *this;
    }

    bool operator==(const point &other) const { return x == other.x && y == other.y; }

    bool operator!=(const point &other) const { return !(*this == other); }

    point operator+(const point &t) const { return point(*this) += t; }

    point operator-(const point &t) const { return point(*this) -= t; }

    point operator*(ld t) const { return point(*this) *= t; }

    point operator/(ld t) const { return point(*this) /= t; }

    point operator-() const { return point(-x, -y); }

    point rotate90() const { return point(-y, x); }

    ld norm() const { return x * x + y * y; }

    ld dist() const { return sqrt((norm())); }

    bool top_half() const { return y > 0 || (y == 0 && x > 0); }

    friend ostream &operator<<(ostream &os, const point &p) { return os << '(' << p.x << ", " << p.y << ')'; }
};

// for z = a * x for example
point operator*(ld a, point b) {
    return b * a;
}

// tested
ld dist(const point &a, const point &b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

// not tested
ld dot(point a, point b) {
    return a.x * b.x + a.y * b.y;
}

// tested
ld cross(point a, point b) {
    return a.x * b.y - a.y * b.x;
}

// tested
point line_intersection(point a, point b, point c, point d) {
    // Line AB represented as a1x + b1y = c1
    ld a1 = b.y - a.y;
    ld b1 = a.x - b.x;
    ld c1 = a1 * (a.x) + b1 * (a.y);

    // Line CD represented as a2x + b2y = c2
    ld a2 = d.y - c.y;
    ld b2 = c.x - d.x;
    ld c2 = a2 * (c.x) + b2 * (c.y);

    ld determinant = a1 * b2 - a2 * b1;


    ld x = (b2 * c1 - b1 * c2) / determinant;
    ld y = (a1 * c2 - a2 * c1) / determinant;
    return {x, y};

}

// tested
int cross_sign(const point &a, const point &b) {
    uint64_t uint64_value = (uint64_t) a.x * b.y - (uint64_t) b.x * a.y;
    ld actual = int64_t(uint64_value);
    return (actual > 0) - (actual < 0);
}


bool collinear(const point &a, const point &b, const point &c) {
    return cross_sign(b - a, c - a) == 0;
}

// 2 * triangle area
ld area_signed_2x(const point &a, const point &b, const point &c) {
    return cross(b - a, c - a);
}

ld perimeter(const point &a, const point &b, const point &c) {
    return dist(a, b) + dist(b, c) + dist(c, a);
}

ld distance_to_line(const point &p, const point &a, const point &b) {
    assert(a != b);
    return (ld) (abs(area_signed_2x(p, a, b))) / (a - b).dist();
}

// Sort in increasing order of y, with ties broken in increasing order of x.
bool yx_compare(const point &a, const point &b) {
    return make_pair(a.y, a.x) < make_pair(b.y, b.x);
}

// Sort in increasing order of angle to the x-axis.
bool angle_compare(const point &a, const point &b) {
    if (a.top_half() ^ b.top_half())
        return a.top_half();

    return cross_sign(a, b) > 0;
}

void run_case(int tc) {
    int n;
    cin >> n;
    vector<array<point, 2>> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i][0].x >> a[i][0].y >> a[i][1].x >> a[i][1].y;
    }

    ld ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                point p1 = line_intersection(a[i][0], a[i][1], a[j][0], a[j][1]);
                point p2 = line_intersection(a[j][0], a[j][1], a[k][0], a[k][1]);
                point p3 = line_intersection(a[k][0], a[k][1], a[i][0], a[i][1]);

                if (collinear(p1, p2, p3)) continue;

                ans = max(ans, perimeter(p1, p2, p3));
            }
        }
    }

    if (ans) cout << ans << el;
    else cout << "no triangle" << el;
}


int32_t main() {
    Nine_seconds        /*Turn Off for Interactive Problems*/

    cout << fixed << setprecision(7) << el;
    int _t = 1;
    //cin >> _t;

    for (int i = 1; i <= _t; i++) {
        run_case(i);
        cout << "\n "[i == _t];
    }
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3812kb

input:

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

output:


no triangle
 

result:

wrong answer