QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189156 | #7065. Triangle | Usernamee | AC ✓ | 1644ms | 3808kb | C++20 | 11.6kb | 2023-09-26 22:00:10 | 2023-09-26 22:00:11 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
// #define int i64
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define fo(i, l, r) for (int i = l; i <= r; i++)
#define of(i, r, l) for (int i = r; i >= l; i--)
#define pii pair<int, int>
#define pb(x...) push_back({x})
using namespace std;
void dbg() {
cerr << endl;
}
template <typename T, typename... Ts>
void dbg(T arg, Ts... args) {
cerr << ' ' << arg;
dbg(args...);
}
#define de(arg...) \
do { \
cerr << "[" #arg "] :"; \
dbg(arg); \
} while (false)
//_______________________________________________________
#include <bits/stdc++.h>
using i64 = long long;
template <class T>
struct Point {
T x;
T y;
Point(T x_ = 0, T y_ = 0)
: x(x_), y(y_) {}
template <class U>
operator Point<U>() {
return Point<U>(U(x), U(y));
}
Point& operator+=(Point p) & {
x += p.x;
y += p.y;
return *this;
}
Point& operator-=(Point p) & {
x -= p.x;
y -= p.y;
return *this;
}
Point& operator*=(T v) & {
x *= v;
y *= v;
return *this;
}
Point& operator/=(T v) & {
x /= v;
y /= v;
return *this;
}
Point operator-() const {
return Point(-x, -y);
}
friend Point operator+(Point a, Point b) {
return a += b;
}
friend Point operator-(Point a, Point b) {
return a -= b;
}
friend Point operator*(Point a, T b) {
return a *= b;
}
friend Point operator/(Point a, T b) {
return a /= b;
}
friend Point operator*(T a, Point b) {
return b *= a;
}
friend bool operator==(Point a, Point b) {
return a.x == b.x && a.y == b.y;
}
friend std::istream& operator>>(std::istream& is, Point& p) {
return is >> p.x >> p.y;
}
friend std::ostream& operator<<(std::ostream& os, Point p) {
return os << "(" << p.x << ", " << p.y << ")";
}
};
template <class T>
T dot(Point<T> a, Point<T> b) {
return a.x * b.x + a.y * b.y;
}
template <class T>
T cross(Point<T> a, Point<T> b) {
return a.x * b.y - a.y * b.x;
}
template <class T>
T square(Point<T> p) {
return dot(p, p);
}
template <class T>
double length(Point<T> p) {
return std::sqrt(double(square(p)));
}
long double length(Point<long double> p) {
return std::sqrt(square(p));
}
template <class T>
Point<T> normalize(Point<T> p) {
return p / length(p);
}
template <class T>
struct Line {
Point<T> a;
Point<T> b;
Line(Point<T> a_ = Point<T>(), Point<T> b_ = Point<T>())
: a(a_), b(b_) {}
};
template <class T>
Point<T> rotate(Point<T> a) {
return Point(-a.y, a.x);
}
template <class T>
int sgn(Point<T> a) {
return a.y > 0 || (a.y == 0 && a.x > 0) ? 1 : -1;
}
template <class T>
bool pointOnLineLeft(Point<T> p, Line<T> l) {
return cross(l.b - l.a, p - l.a) > 0;
}
template <class T>
Point<T> lineIntersection(Line<T> l1, Line<T> l2) {
return l1.a + (l1.b - l1.a) * (cross(l2.b - l2.a, l1.a - l2.a) / cross(l2.b - l2.a, l1.a - l1.b));
}
template <class T>
bool pointOnSegment(Point<T> p, Line<T> l) {
return cross(p - l.a, l.b - l.a) == 0 && std::min(l.a.x, l.b.x) <= p.x && p.x <= std::max(l.a.x, l.b.x) && std::min(l.a.y, l.b.y) <= p.y && p.y <= std::max(l.a.y, l.b.y);
}
template <class T>
bool pointInPolygon(Point<T> a, std::vector<Point<T>> p) {
int n = p.size();
for (int i = 0; i < n; i++) {
if (pointOnSegment(a, Line(p[i], p[(i + 1) % n]))) {
return true;
}
}
int t = 0;
for (int i = 0; i < n; i++) {
auto u = p[i];
auto v = p[(i + 1) % n];
if (u.x < a.x && v.x >= a.x && pointOnLineLeft(a, Line(v, u))) {
t ^= 1;
}
if (u.x >= a.x && v.x < a.x && pointOnLineLeft(a, Line(u, v))) {
t ^= 1;
}
}
return t == 1;
}
// 0 : not intersect
// 1 : strictly intersect
// 2 : overlap
// 3 : intersect at endpoint
template <class T>
std::tuple<int, Point<T>, Point<T>> segmentIntersection(Line<T> l1, Line<T> l2) {
if (std::max(l1.a.x, l1.b.x) < std::min(l2.a.x, l2.b.x)) {
return {0, Point<T>(), Point<T>()};
}
if (std::min(l1.a.x, l1.b.x) > std::max(l2.a.x, l2.b.x)) {
return {0, Point<T>(), Point<T>()};
}
if (std::max(l1.a.y, l1.b.y) < std::min(l2.a.y, l2.b.y)) {
return {0, Point<T>(), Point<T>()};
}
if (std::min(l1.a.y, l1.b.y) > std::max(l2.a.y, l2.b.y)) {
return {0, Point<T>(), Point<T>()};
}
if (cross(l1.b - l1.a, l2.b - l2.a) == 0) {
if (cross(l1.b - l1.a, l2.a - l1.a) != 0) {
return {0, Point<T>(), Point<T>()};
} else {
auto maxx1 = std::max(l1.a.x, l1.b.x);
auto minx1 = std::min(l1.a.x, l1.b.x);
auto maxy1 = std::max(l1.a.y, l1.b.y);
auto miny1 = std::min(l1.a.y, l1.b.y);
auto maxx2 = std::max(l2.a.x, l2.b.x);
auto minx2 = std::min(l2.a.x, l2.b.x);
auto maxy2 = std::max(l2.a.y, l2.b.y);
auto miny2 = std::min(l2.a.y, l2.b.y);
Point<T> p1(std::max(minx1, minx2), std::max(miny1, miny2));
Point<T> p2(std::min(maxx1, maxx2), std::min(maxy1, maxy2));
if (!pointOnSegment(p1, l1)) {
std::swap(p1.y, p2.y);
}
if (p1 == p2) {
return {3, p1, p2};
} else {
return {2, p1, p2};
}
}
}
auto cp1 = cross(l2.a - l1.a, l2.b - l1.a);
auto cp2 = cross(l2.a - l1.b, l2.b - l1.b);
auto cp3 = cross(l1.a - l2.a, l1.b - l2.a);
auto cp4 = cross(l1.a - l2.b, l1.b - l2.b);
if ((cp1 > 0 && cp2 > 0) || (cp1 < 0 && cp2 < 0) || (cp3 > 0 && cp4 > 0) || (cp3 < 0 && cp4 < 0)) {
return {0, Point<T>(), Point<T>()};
}
Point p = lineIntersection(l1, l2);
if (cp1 != 0 && cp2 != 0 && cp3 != 0 && cp4 != 0) {
return {1, p, p};
} else {
return {3, p, p};
}
}
template <class T>
bool segmentInPolygon(Line<T> l, std::vector<Point<T>> p) {
int n = p.size();
if (!pointInPolygon(l.a, p)) {
return false;
}
if (!pointInPolygon(l.b, p)) {
return false;
}
for (int i = 0; i < n; i++) {
auto u = p[i];
auto v = p[(i + 1) % n];
auto w = p[(i + 2) % n];
auto [t, p1, p2] = segmentIntersection(l, Line(u, v));
if (t == 1) {
return false;
}
if (t == 0) {
continue;
}
if (t == 2) {
if (pointOnSegment(v, l) && v != l.a && v != l.b) {
if (cross(v - u, w - v) > 0) {
return false;
}
}
} else {
if (p1 != u && p1 != v) {
if (pointOnLineLeft(l.a, Line(v, u)) || pointOnLineLeft(l.b, Line(v, u))) {
return false;
}
} else if (p1 == v) {
if (l.a == v) {
if (pointOnLineLeft(u, l)) {
if (pointOnLineLeft(w, l) && pointOnLineLeft(w, Line(u, v))) {
return false;
}
} else {
if (pointOnLineLeft(w, l) || pointOnLineLeft(w, Line(u, v))) {
return false;
}
}
} else if (l.b == v) {
if (pointOnLineLeft(u, Line(l.b, l.a))) {
if (pointOnLineLeft(w, Line(l.b, l.a)) && pointOnLineLeft(w, Line(u, v))) {
return false;
}
} else {
if (pointOnLineLeft(w, Line(l.b, l.a)) || pointOnLineLeft(w, Line(u, v))) {
return false;
}
}
} else {
if (pointOnLineLeft(u, l)) {
if (pointOnLineLeft(w, Line(l.b, l.a)) || pointOnLineLeft(w, Line(u, v))) {
return false;
}
} else {
if (pointOnLineLeft(w, l) || pointOnLineLeft(w, Line(u, v))) {
return false;
}
}
}
}
}
}
return true;
}
template <class T>
std::vector<Point<T>> hp(std::vector<Line<T>> lines) {
std::sort(lines.begin(), lines.end(), [&](auto l1, auto l2) {
auto d1 = l1.b - l1.a;
auto d2 = l2.b - l2.a;
if (sgn(d1) != sgn(d2)) {
return sgn(d1) == 1;
}
return cross(d1, d2) > 0;
});
std::deque<Line<T>> ls;
std::deque<Point<T>> ps;
for (auto l : lines) {
if (ls.empty()) {
ls.push_back(l);
continue;
}
while (!ps.empty() && !pointOnLineLeft(ps.back(), l)) {
ps.pop_back();
ls.pop_back();
}
while (!ps.empty() && !pointOnLineLeft(ps[0], l)) {
ps.pop_front();
ls.pop_front();
}
if (cross(l.b - l.a, ls.back().b - ls.back().a) == 0) {
if (dot(l.b - l.a, ls.back().b - ls.back().a) > 0) {
if (!pointOnLineLeft(ls.back().a, l)) {
assert(ls.size() == 1);
ls[0] = l;
}
continue;
}
return {};
}
ps.push_back(lineIntersection(ls.back(), l));
ls.push_back(l);
}
while (!ps.empty() && !pointOnLineLeft(ps.back(), ls[0])) {
ps.pop_back();
ls.pop_back();
}
if (ls.size() <= 2) {
return {};
}
ps.push_back(lineIntersection(ls[0], ls.back()));
return std::vector(ps.begin(), ps.end());
}
using P = Point<i64>;
using ld = long double;
void solve() {
array<P, 3> a;
fo(i, 0, 2) cin >> a[i];
P p;
cin >> p;
P A, B, C;
bool ok = 0;
fo(i, 0, 2) {
int j = (i + 1) % 3;
Line l(a[i], a[j]);
if (pointOnSegment(p, l)) {
ok = 1;
A = a[i];
B = a[j];
C = a[(j + 1) % 3];
break;
}
}
if (!ok) {
cout << "-1\n";
return;
}
using Pl = Point<ld>;
Pl D = p;
Pl S, T;
if (square(A - p) == square(B - p)) {
cout << C.x << ' ' << C.y << "\n";
return;
} else if (square(A - p) < square(B - p)) {
S = B, T = C;
} else {
S = A, T = C;
}
auto area = [&](auto& a) {
ld s = 0;
fo(i, 0, 2) {
s += cross(a[i], a[(i + 1) % 3]);
}
return abs(s);
};
ld s0 = area(a);
ld lo = 0, hi = 1, eps = 1e-10;
array<Pl, 3> b;
b[0] = S, b[1] = p;
while (hi - lo > eps) {
double mi = (hi + lo) / 2.0;
Pl E = S + (T - S) * mi;
b[2] = E;
double s1 = area(b);
if (s1 * 2 > s0)
hi = mi;
else
lo = mi;
}
Pl E = S + (T - S) * lo;
cout << E.x << ' ' << E.y << "\n";
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(10);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3692kb
input:
2 0 0 1 1 1 0 1 0 0 0 1 1 1 0 2 0
output:
0.5000000000 0.5000000000 -1
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 569ms
memory: 3632kb
input:
999966 9456 15557 18451 3957 6242 20372 9855 5351 30245 31547 9979 4703 25914 19144 26670 11383 13855 0 24614 0 15860 11017 12445 0 27870 17680 4219 3554 9129 29072 28316 17893 3249 27269 12754 4923 31746 16860 14894 21576 6846 0 1915 0 25023 28721 10508 0 10110 11862 23224 10373 17715 8212 29474 11...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 21424.6814792306 13086.0539108116 -1 -1 18711.2379901239 10162.3763766289 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 28212.9521348395 245.8177862319 -1 -1 -1 -1 -1 -1 -1 -1 22604.5753011541 14546.1287149927 -1 -1 11557.3465216421 46...
result:
ok 1111378 numbers
Test #3:
score: 0
Accepted
time: 607ms
memory: 3808kb
input:
999974 9228 16833 13143 23461 5117 7645 21359 13652 21313 3160 20333 1620 16288 7781 13315 10132 4372 0 27536 0 3207 8695 9983 0 21469 29998 19948 29904 30517 11141 14857 12881 11116 29172 16833 32095 18915 9448 22043 12275 32131 0 14304 0 16638 29018 2048 0 4695 4823 14130 2496 32676 4092 6363 2476...
output:
-1 -1 11482.9903726345 5737.2238361603 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 15409.8418552561 12451.4278633631 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10828.9713856068 25347.3348568589 -1 -1 -1 -1 -1 18768.6727002214 12151.3671503242 -1 -1 -1 -1 -1 10801.120...
result:
ok 1110866 numbers
Test #4:
score: 0
Accepted
time: 1644ms
memory: 3692kb
input:
1000000 54242 34392 23333 92971 5711 47765 54242 34392 24492 41078 36756 68794 2060 62118 14678 50283 12685 18891 59613 23256 26016 46755 59613 23256 85238 49611 95092 85360 45143 87657 95092 85360 72852 37174 39825 60628 32289 18423 72852 37174 95309 61613 1645 45877 78395 38196 95309 61613 92215 7...
output:
14522.0000000000 70368.0000000000 32900.8888884401 68052.2222221359 19350.5000000000 32823.0000000000 65190.5000000000 68634.0000000000 36057.0000000000 39525.5000000000 40020.0000000000 42036.5000000000 95183.5000000000 40970.5000000000 28582.0000000000 94834.5000000000 55598.0000000000 59174.00000...
result:
ok 2000000 numbers