QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#218194#2434. Single Cut of FailureKronos#WA 0ms4072kbC++174.8kb2023-10-17 20:09:222023-10-17 20:09:23

Judging History

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

  • [2023-10-17 20:09:23]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4072kb
  • [2023-10-17 20:09:22]
  • 提交

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

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 4072kb