QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372149#2434. Single Cut of FailureUFRJ#WA 1ms3612kbC++204.7kb2024-03-30 23:48:372024-03-30 23:48:38

Judging History

你现在查看的是最新测评结果

  • [2024-03-30 23:48:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3612kb
  • [2024-03-30 23:48:37]
  • 提交

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;
}

Details

Test #1:

score: 100
Accepted
time: 1ms
memory: 3544kb

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3612kb