QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#372149 | #2434. Single Cut of Failure | UFRJ# | WA | 1ms | 3612kb | C++20 | 4.7kb | 2024-03-30 23:48:37 | 2024-03-30 23:48:38 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
using lint = int64_t;
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); }
bool operator==(P p) const {return tie(x, y) == tie(p.x, p.y); }
P operator+(P p) const { return P(p.x+x, p.y+y); }
P operator-(P p) const { return P(p.x-x, p.y-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); }
};
using P = Point<int64_t>;
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(void) {
cin.tie(nullptr)->sync_with_stdio(false);
int n, w, h;
cin >> n >> w >> h;
h = 2*h; w = 2*w;
vector<pair<P,P>> v(n);
for(int i = 0; i < n; i++) {
P a, b;
cin>>a.x>>a.y;
cin>>b.x>>b.y;
a = a*2; b = b*2;
v[i] = {a, b};
if(!(a<b)) swap(a, b);
}
auto print = [&](int64_t x) -> void {
if(x%2) cout<<(x/2)<<".5";
else cout<<x/2;
};
auto solve = [&](vector<pair<P,P>> v, int h, int w) -> pair<bool, pair<P,P>> {
vector<P> left, right;
{
int64_t minUp = h, maxUp = 0;
int64_t minDown = h, maxDown = 0;
for(auto [A, B] : v){
if(!(A < B)) swap(A, B);
if(A.x == 0){
if(A.y <= B.y){
minUp = min(minUp, A.y);
maxUp = max(maxUp, A.y);
}
if(A.y >= B.y){
minDown = min(minDown, A.y);
maxDown = max(maxDown, A.y);
}
}
}
left = {P(0,minUp), P(0,maxUp), P(0,minDown), P(0,maxDown)};
}
{
int64_t minUp = h, maxUp = 0;
int64_t minDown = h, maxDown = 0;
for(auto [A, B] : v){
if(A < B) swap(A, B);
if(A.x == w){
if(A.y <= B.y){
minUp = min(minUp, A.y);
maxUp = max(maxUp, A.y);
}
if(A.y >= B.y){
minDown = min(minDown, A.y);
maxDown = max(maxDown, A.y);
}
}
}
right = {P(w,minUp), P(w,maxUp), P(w,minDown), P(w,maxDown)};
}
for(P s : left) for(P t : right){
for(auto [d1,d2] : vector<pair<int, int>>{{1,1},{1,-1},{-1,1},{-1,-1}}){
P a = s; s.y += d1;
P b = t; t.y += d2;
if(s.y < 0 || s.y > h) continue;
if(t.y < 0 || t.y > h) continue;
int cnt = 0;
for(auto [A, B] : v){
if(segInter(A,B,a,b).size()){
cnt++;
}
}
if(cnt == n){
return {true, {s,t}};
}
}
}
return {false, {{},{}}};
};
auto [ok, p] = solve(v, h, w);
if(ok){
cout<<"1\n";
auto [a,b] = p;
print(a.x); cout<<" ";
print(a.y); cout<<" ";
print(b.x); cout<<" ";
print(b.y); cout<<"\n";
exit(0);
}
for(auto &[a, b] : v){
swap(a.x, a.y);
swap(b.x, b.y);
}
swap(h, w);
tie(ok, p) = solve(v, h, w);
if(ok){
cout<<"1\n";
auto [a,b] = p;
print(a.y); cout<<" ";
print(a.x); cout<<" ";
print(b.y); cout<<" ";
print(b.x); cout<<"\n";
exit(0);
}
cout<<"2\n";
print(1); cout<<" ";
print(1); cout<<" ";
print(w); cout<<" ";
print(h-1); cout<<" ";
cout<<"\n";
print(1); cout<<" ";
print(h-1); cout<<" ";
print(w); cout<<" ";
print(1); cout<<" ";
cout<<"\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3544kb
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3612kb