QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218194 | #2434. Single Cut of Failure | Kronos# | WA | 0ms | 4072kb | C++17 | 4.8kb | 2023-10-17 20:09:22 | 2023-10-17 20:09:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
struct debug {
#define contPrint { *this << "["; \
int f = 0; for(auto it : x) { *this << (f?", ":""); *this << it; f = 1;} \
*this << "]"; return *this;}
~debug(){cerr << endl;}
template<class c> debug& operator<<(c x) {cerr << x; return *this;}
template<class c, class d>
debug& operator<<(pair<c, d> x) {*this << "(" << x.first << ", " << x.second << ")";
return *this;}
template<class c> debug& operator<<(vector<c> x) contPrint;
#undef contPrint
};
#define dbg(x) "[" << #x << ": " << x << "] "
#define Wa() cerr << "[LINE: " << __LINE__ << "] -> "; debug() <<
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template <class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator <(P p) const { return tie(x, y) < tie(p.x, p.y); }
P operator + (P p) const { return P(x + p.x, y + p.y); }
P operator - (P p) const { return P(x - p.x, y - p.y); }
P operator * (T d) const { return P(x * d, y * d); }
P operator / (T d) const { return P(x / d, y / d); }
T dot(P p) const { return x * p.x + y * p.y; }
T cross(P p) const { return x * p.y - y * p.x; }
T cross(P a, P b) const { return (a - *this).cross(b - *this); }
T dist2() const { return x * x + y * y; }
double dist() const { return sqrt((double) dist2()); }
double angle() const { return atan2(y, x); }
P unit() const { return *this / dist(); }
P perp() const { return P(-y, x); }
};
template <class P> bool onSegment(P s, P e, P p) {
return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}
template <class P> vector <P> segInter(P a, P b, P c, P d) {
auto oa = c.cross(d, a), ob = c.cross(d, b),
oc = a.cross(b, c), od = a.cross(b, d);
if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0)
return {(a * ob - b * oa) / (ob - oa)};
set <P> s;
if (onSegment(c, d, a)) s.insert(a);
if (onSegment(c, d, b)) s.insert(b);
if (onSegment(a, b, c)) s.insert(c);
if (onSegment(a, b, d)) s.insert(d);
return {s.begin(), s.end()};
}
int main()
{
i64 n, h, w;
scanf("%lld %lld %lld", &n, &w, &h);
int st_x = -1e9;
int ed_x = 1e9;
int st_y = -1e9;
int ed_y = 1e9;
vector<array<int, 4>> segs;
for(int i = 0; i < n; i++) {
int a, b, x, y;
scanf("%d %d %d %d", &a, &b, &x, &y);
if(a <= x) {
st_x = max(st_x, a);
ed_x = min(ed_x, x);
} else {
st_x = max(st_x, x);
ed_x = min(ed_x, a);
}
if(b <= y) {
st_y = max(st_y, b);
ed_y = min(ed_y, y);
} else {
st_y = max(st_y, y);
ed_y = min(ed_y, b);
}
segs.push_back({a, b, x, y});
}
bool ok = true;
for(int i = 0; i < n; i++) {
Point<double> p1(segs[i][0], segs[i][1]);
Point<double> p2(segs[i][2], segs[i][3]);
Point<double> p3(ed_x, 0);
Point<double> p4(st_x, h);
if(segInter(p1, p2, p3, p4).size() == 0) {
ok = false;
}
}
if(ok) {
puts("1");
printf("%d %d %d %d\n", st_x, (int)h, ed_x, 0);
return 0;
}
ok = true;
for(int i = 0; i < n; i++) {
Point<double> p1(segs[i][0], segs[i][1]);
Point<double> p2(segs[i][2], segs[i][3]);
Point<double> p3(ed_x, h);
Point<double> p4(st_x, 0);
if(segInter(p1, p2, p3, p4).size() == 0) {
ok = false;
}
}
if(ok) {
puts("1");
printf("%d %d %d %d\n", st_x, 0, ed_x, h);
return 0;
}
ok = true;
for(int i = 0; i < n; i++) {
Point<double> p1(segs[i][0], segs[i][1]);
Point<double> p2(segs[i][2], segs[i][3]);
Point<double> p3(0, st_y);
Point<double> p4(w, ed_y);
if(segInter(p1, p2, p3, p4).size() == 0) {
ok = false;
}
}
if(ok) {
puts("1");
printf("%d %d %d %d\n", 0, st_y, (int)w, ed_y);
return 0;
}
ok = true;
for(int i = 0; i < n; i++) {
Point<double> p1(segs[i][0], segs[i][1]);
Point<double> p2(segs[i][2], segs[i][3]);
Point<double> p3(w, st_y);
Point<double> p4(0, ed_y);
if(segInter(p1, p2, p3, p4).size() == 0) {
ok = false;
}
}
if(ok) {
puts("1");
printf("%d %d %d %d\n", w, st_y, (int)0, ed_y);
return 0;
}
puts("2");
printf("%d %d %d %d\n", 0, 0, w, h);
printf("%d %d %d %d\n", 0, h, w, 0);
}
Details
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 4072kb