QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373176 | #3663. The Biggest Triangle | MahmoudBassem | AC ✓ | 19ms | 4048kb | C++20 | 4.7kb | 2024-04-01 05:35:23 | 2024-04-01 05:35:24 |
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
pair<bool, 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;
if (!determinant) return {};
ld x = (b2 * c1 - b1 * c2) / determinant;
ld y = (a1 * c2 - a2 * c1) / determinant;
return {true, {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++) {
auto[b1, p1] = line_intersection(a[i][0], a[i][1], a[j][0], a[j][1]);
auto[b2, p2] = line_intersection(a[j][0], a[j][1], a[k][0], a[k][1]);
auto[b3, p3] = line_intersection(a[k][0], a[k][1], a[i][0], a[i][1]);
if (!b1 || !b2 || !b3) {
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: 100
Accepted
time: 1ms
memory: 3852kb
input:
3 0 0 0 1 0 0 1 0 0 1 1 0
output:
3.4142136
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
3 0 0 0 1 0 0 1 0 0 0 1 1
output:
no triangle
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
4 0 0 0 1 0 4 3 0 0 0 1 0 -1 -1 1 1
output:
12.0000000
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
20 0 0 10 1 0 0 18 1 0 0 16 1 0 0 14 1 0 0 0 1 0 0 17 1 0 0 11 1 0 0 2 1 0 0 3 1 0 0 9 1 0 0 5 1 0 0 7 1 0 0 4 1 0 0 19 1 0 0 6 1 0 0 15 1 0 0 8 1 0 0 1 1 0 0 13 1 0 0 12 1
output:
no triangle
result:
ok
Test #5:
score: 0
Accepted
time: 19ms
memory: 3744kb
input:
100 -1086 -690 -818 616 2109 2485 -455 -560 31 -680 -260 -804 -427 2531 88 418 -852 -982 -57 14 -361 -5831 121 -1255 443 79 974 -592 -1946 1682 -1884 589 -941 69 -910 -611 74 -292 -616 714 3574 3254 908 562 -4123 -301 961 167 -245 -836 -571 781 844 62 -320 304 789 -295 -88 -637 1199 1365 -616 -1508 ...
output:
12352116.2772079
result:
ok
Test #6:
score: 0
Accepted
time: 19ms
memory: 3796kb
input:
100 -944 5551 -400 1443 504 -1168 1536 -466 1475 668 -404 -570 -390 -63 -1717 101 923 4554 -466 -1679 2307 566 1115 525 193 -48 -274 699 -3079 -3465 588 1087 -252 -1408 -1153 -24 4471 -1055 988 -373 48 248 -469 -1307 3143 2560 829 927 1079 -170 36 396 -1156 -2459 471 245 353 2927 752 1406 -3767 1685...
output:
2553320.2934668
result:
ok
Test #7:
score: 0
Accepted
time: 19ms
memory: 3756kb
input:
100 -962 186 663 -478 -860 -786 852 -406 -1648 634 1159 -805 3699 5438 631 947 -685 -698 -990 194 7466 -3888 1558 -983 -1001 -3536 523 1280 2967 -381 -1373 -177 -1974 -1207 -748 -626 1537 -534 -530 416 2268 3597 -794 -1538 885 814 -656 -948 2231 2096 -517 -525 437 -1599 926 -1428 5689 -1284 -1365 24...
output:
6418642.3313375
result:
ok
Test #8:
score: 0
Accepted
time: 19ms
memory: 3752kb
input:
100 7722 -3104 -9865 -5532 7394 6046 113 2456 7823 7603 -7836 -7435 9819 6146 -9499 -3317 3741 1796 226 -7257 -9239 -2165 -9087 9264 6798 2042 -4975 5261 -1533 -6390 9448 4652 -876 -2807 2540 2584 6607 1133 -2519 9340 -1354 -7085 -8558 -4928 339 9142 8466 5893 -7926 7279 5710 4244 467 2633 -9205 -61...
output:
57991431.1663617
result:
ok
Test #9:
score: 0
Accepted
time: 19ms
memory: 3852kb
input:
100 -7986 1112 -5473 358 -1009 5926 5769 9954 832 -1167 -7448 5029 -4771 -6472 6791 -1515 8314 3256 9923 4673 3804 -4789 9905 3734 -5859 -6317 9153 -6349 -3905 5803 -360 -6723 3951 -1408 -952 -6375 1655 6681 7564 -7552 -9736 -8660 9917 -9515 -5462 -5974 3372 2617 5772 -9114 265 -5399 -7213 2846 8979...
output:
1030246220.3070990
result:
ok
Test #10:
score: 0
Accepted
time: 19ms
memory: 3896kb
input:
100 -5876 7730 8652 -5022 -8861 7 4538 6916 8856 3626 -3115 5358 -3334 2826 -7126 -6803 7540 3176 -6016 6604 5288 -4498 -8943 -3397 -2365 -2113 -6883 9611 2385 3319 -7718 7955 -3033 7224 -3489 -2841 6114 -7023 -3727 -6736 6816 -5733 9785 -3601 8030 8901 7032 4143 9685 2940 -1412 5444 9754 -9054 1494...
output:
60810745.8854596
result:
ok
Test #11:
score: 0
Accepted
time: 19ms
memory: 3804kb
input:
100 5302 4446 2050 -9610 -3532 8582 -3315 -7768 6067 -5691 -7125 7006 8151 3269 -860 -3189 -7421 4027 -9253 7843 5636 1230 -9906 -3523 -329 3725 4708 6837 -709 -7897 -8726 -7180 1342 2416 3517 2483 -2392 -721 5882 3124 8146 -9979 4251 -546 5896 -4954 3077 4140 2939 9208 9682 -105 5390 7945 2113 -37 ...
output:
34329826.3912494
result:
ok
Test #12:
score: 0
Accepted
time: 19ms
memory: 4048kb
input:
100 5429 -7445 8797 7155 -8344 -5436 5284 8452 -5564 8453 -1537 -7348 -89 1689 -5722 5332 2144 -8599 808 -6617 -6701 -6394 41 103 9009 1969 -4086 -9768 5566 3269 3257 -2990 -7008 3689 -1258 5935 4153 6148 2346 -5235 4064 -3261 3896 -3707 -1231 -7651 -5516 5236 546 1890 -453 4741 1258 -1938 -4683 511...
output:
105643194.5634676
result:
ok
Test #13:
score: 0
Accepted
time: 19ms
memory: 3748kb
input:
100 -516 512 6556 -4112 22 -1138 2482 -150 -180 -839 -1467 -1142 -621 -559 6871 -899 120 -796 2384 -492 -762 -703 -2776 -762 -262 -631 -956 -1249 -1152 1225 -5960 4963 -1261 187 1252 -644 -1411 -710 -4074 -776 -233 1135 -1737 -7165 208 563 -2243 -3946 476 -225 -1076 613 1393 57 -6615 -3931 -476 -441...
output:
6543389.9889371
result:
ok
Test #14:
score: 0
Accepted
time: 15ms
memory: 3756kb
input:
100 521 -356 3537 -2756 1015 790 -987 844 405 -1097 -1793 993 1134 -361 4790 -979 -866 -317 -350 478 67 -1313 -2041 3001 855 -1197 -6513 6967 1171 -65 -3145 1753 333 -355 -987 844 554 -128 2095 -1100 446 -144 -694 -52 -243 1131 208 2314 -362 198 -30 448 928 169 -3938 -494 -500 -1401 -1082 2646 533 -...
output:
211316352.8159677
result:
ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
3 0 1 1 -1 0 -1 1 1 0 3 1 -3
output:
no triangle
result:
ok
Test #16:
score: 0
Accepted
time: 19ms
memory: 4028kb
input:
100 305 1242 -2963 702 286 469 -1310 1745 -766 -708 -1174 -399 -832 364 -1472 -1122 623 124 -3301 -4440 -1328 308 -3268 2958 88 -124 534 769 262 1136 1036 1165 1234 -1054 -1950 -980 384 1217 -2304 887 53 -334 -769 -1700 -347 -1389 -512 1107 439 846 -512 1107 -257 1258 -1277 654 -235 56 -481 -2090 75...
output:
7359005.2176760
result:
ok
Test #17:
score: 0
Accepted
time: 19ms
memory: 3856kb
input:
100 490 -1236 -1193 5733 -613 722 4335 3362 -815 -563 2063 3327 1070 220 3352 -1514 -766 457 4794 4157 1187 -1224 3703 -5846 1130 -997 -3674 7339 -663 367 -71 1087 -1366 1004 3814 1336 -1100 -511 -3158 -3707 335 327 624 1382 -655 -135 1681 4753 -322 1297 682 457 1323 868 2022 354 -156 1287 -1716 109...
output:
4311750.9313019
result:
ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
20 0 13 1 13 0 11 1 11 0 16 1 16 0 0 1 0 0 17 1 17 0 4 1 4 0 14 1 14 0 7 1 7 0 18 1 18 0 19 1 19 0 12 1 12 0 6 1 6 0 5 1 5 0 1 1 1 0 8 1 8 0 15 1 15 0 10 1 10 0 2 1 2 0 3 1 3 0 9 1 9
output:
no triangle
result:
ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
20 18 0 18 1 19 0 19 1 17 0 17 1 7 0 7 1 4 0 4 1 16 0 16 1 6 0 6 1 8 0 8 1 9 0 9 1 14 0 14 1 1 0 1 1 13 0 13 1 5 0 5 1 11 0 11 1 3 0 3 1 10 0 10 1 15 0 15 1 0 0 0 1 12 0 12 1 2 0 2 1
output:
no triangle
result:
ok
Test #20:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
40 0 0 1 0 4 0 4 1 0 15 1 15 0 6 1 6 0 18 1 18 0 10 1 10 12 0 12 1 0 11 1 11 17 0 17 1 0 17 1 17 2 0 2 1 8 0 8 1 0 13 1 13 7 0 7 1 0 0 0 1 15 0 15 1 0 4 1 4 14 0 14 1 11 0 11 1 6 0 6 1 0 12 1 12 0 5 1 5 9 0 9 1 0 16 1 16 0 8 1 8 0 19 1 19 3 0 3 1 0 2 1 2 10 0 10 1 16 0 16 1 1 0 1 1 0 1 1 1 19 0 19 1...
output:
no triangle
result:
ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
20 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -10000 9995 9983 -10000 -1...
output:
no triangle
result:
ok
Test #22:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
20 -10000 -10000 9991 9979 -10000 -10000 9987 9975 -10000 -10000 9983 9971 -10000 -10000 9988 9976 -10000 -10000 9994 9982 -10000 -10000 9989 9977 -10000 -10000 9992 9980 -10000 -10000 9984 9972 -10000 -10000 9977 9965 -10000 -10000 9980 9968 -10000 -10000 9978 9966 -10000 -10000 9976 9964 -10000 -1...
output:
no triangle
result:
ok
Test #23:
score: 0
Accepted
time: 19ms
memory: 4036kb
input:
100 -103 -1625 -450 -1632 610 1988 363 16 165 -681 360 1785 -98 942 -235 -142 300 -614 241 700 222 887 -95 363 1075 3666 -270 -1180 240 -956 -602 968 2746 1901 -746 -231 -1399 -3994 541 1735 716 847 881 166 -711 866 333 -924 -642 -973 -35 395 -505 -96 -94 214 393 -849 -946 -746 -942 509 -1549 -859 4...
output:
2516645.8676899
result:
ok
Test #24:
score: 0
Accepted
time: 19ms
memory: 3812kb
input:
100 -42 639 684 679 4015 -1043 -901 250 -601 -215 604 590 4730 2714 1127 643 932 1353 518 884 294 -846 958 -909 258 294 912 -309 165 -411 -269 -4 -2667 245 -495 1 -1447 -1809 -124 -1558 -869 2139 272 -625 -1232 3960 -260 930 -481 -2758 -291 -561 -1160 1188 -305 847 -664 -666 -439 -603 461 273 -394 6...
output:
75090836.2387869
result:
ok