QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373174 | #3663. The Biggest Triangle | MahmoudBassem | WA | 1ms | 3812kb | C++20 | 4.6kb | 2024-04-01 05:29:31 | 2024-04-01 05:29:33 |
Judging History
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