QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#73085#5155. Faster Than LightSorting#WA 2ms7568kbC++4.8kb2023-01-21 23:50:072023-01-21 23:56:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-21 23:56:56]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7568kb
  • [2023-01-21 23:50:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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(x - p.x, y - p.y);}
    P operator+(P p) const {return P(x + p.x, y + p.y);}
    T cross(P p) const {return x * p.y - y * p.x;}
    T dot(P p) const {return x * p.x + y * p.y; }
    T cross(P a, P b) const {return (a - *this).cross(b - *this);}
};

struct Angle{
    ll x, y;
    ll t;
    Angle(ll x, ll y, ll t = 0): x(x), y(y), t(t){}
    Angle(Point<ll> p): x(p.x), y(p.y), t(0){}
    int half() const {
        assert(x || y);
        return y < 0 || (y == 0 && x < 0);
    }
};

bool operator<(Angle a, Angle b){
    return make_tuple(a.t, a.half(), a.y * b. x) <
           make_tuple(b.t, b.half(), a.x * b.y);
}

const int N = 2e5 + 3;

int n;
ll x1[N], yedno[N], x2[N], y2[N];

#define all(x) (x).begin(), (x).end()

typedef Point<ll> P;
vector<P> convexHull(vector<P> pts) {
    if(pts.size() <= 1) return pts;
    sort(all(pts));
    vector<P> h((int)pts.size() + 1);
    int s = 0, t = 0;
    for(int it = 2; it--; s = --t, reverse(all(pts))){
        for(P p: pts){
            while(t >= s + 2 && h[t - 2].cross(h[t - 1], p) <= 0) t--;
            h[t++] = p;
        }
    }
    return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
}

template<class P>
int sideOf(P s, P e, P p){ return sgn(s.cross(e, p)); }

bool onSegment(P s, P e, P p){
    return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}

bool inHull(const vector<P> &l, P p, bool strict = true){
    int a = 1, b = (int)l.size() - 1, r = !strict;
    if(l.size() < 3) return r && onSegment(l[0], l.back(), p);
    if(sideOf(l[0], l[a], l[b]) > 0) swap(a, b);
    if(sideOf(l[0], l[a], p) >= r || sideOf(l[0], l[b], p) <= -r)
        return false;
    while(abs(a - b) > 1){
        int c = (a + b) / 2;
        (sideOf(l[0], l[c], p) > 0 ? b : a) = c;
    }
    return sgn(l[a].cross(l[b], p)) < r;
}

bool inPolygon(vector<P> &p, P a, bool strict = true){
    int cnt = 0, n = p.size();
    for(int i = 0; i < n; ++i){
        P q = p[(i + 1) % n];
        if(onSegment(p[i], q, a)) return !strict;
        cnt ^= ((a.y < p[i].y) - (a.y < q.y)) * a.cross(p[i], q) > 0;
    }
    return cnt;
}

/*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(ons)
}*/

bool check(const vector<Point<ll>> &in, vector<Point<ll>> out){
    vector<Point<ll>> ch1 = convexHull(in); 
    for(auto &p: out)
        p = Point<ll>{-p.x, -p.y};
    vector<Point<ll>> ch2 = convexHull(out);

    // for(auto [x, y]: ch1)
        // cout << x << "," << y << " ";
    // cout << endl;
    // cout << "Ch2 ";
    // for(auto [x, y]: ch2)
        // cout << x << "," << y << " ";
    // cout << endl;

    assert(ch1.size() != 2 && ch2.size() != 2);

    ch1.push_back(ch1[0]);
    ch2.push_back(ch2[0]);

    int i = 1, j = 1;
    vector<Point<ll>> v;
    v.push_back(ch1[0] + ch2[0]);
    while(i < ch1.size() && j < ch2.size()){
        Angle a1(ch1[i] - ch1[i - 1]);
        Angle a2(ch2[j] - ch2[j - 1]);
        if(a1 < a2){
            v.push_back(v.back() + ch1[i] - ch1[i - 1]);
            ++i;
        }
        else{
            v.push_back(v.back() + ch2[j] - ch2[j - 1]);
            ++j;
        }
    }
    while(i < ch1.size()){
        v.push_back(v.back() + ch1[i] - ch1[i - 1]);
        ++i;
    }
    while(j < ch2.size()){
        v.push_back(v.back() + ch2[j] - ch2[j - 1]);
        ++j;
    }
    v.pop_back();

    // cout << "v: ";
    // for(auto [x, y]: v)
        // cout << x << "," << y << " ";
    // cout << endl;

    return !inPolygon(v, Point<ll>(0, 0), true);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> x1[i] >> yedno[i] >> x2[i] >> y2[i];

    if(n <= 2){
        cout << "possible\n";
        return 0;
    }

    vector<Point<ll>> in1, in2, out1, out2;
    for(int i = 0; i < n; ++i){
        in1.push_back(Point<ll>(x1[i], yedno[i]));
        in2.push_back(Point<ll>(x1[i], y2[i]));
        out1.push_back(Point<ll>(x2[i], y2[i]));
        out2.push_back(Point<ll>(x2[i], yedno[i]));
    }

    if(check(in1, out1) || check(in2, out2))
        cout << "possible\n";
    else
        cout << "impossible\n";
}
/*
3
1 1 2 2
2 2 3 3
3 3 4 4
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7568kb

input:

5
1 3 3 4
2 2 4 3
4 1 5 3
5 2 7 3
6 3 8 4

output:

possible

result:

ok single line: 'possible'

Test #2:

score: 0
Accepted
time: 2ms
memory: 7468kb

input:

4
1 1 2 2
1 3 2 4
3 1 4 2
3 3 4 4

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 2ms
memory: 7472kb

input:

3
1 1 2 2
1 3 2 4
3 3 4 4

output:

possible

result:

ok single line: 'possible'

Test #4:

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

input:

5
0 0 1 999999999
0 999999999 999999999 1000000000
1 0 999999998 1
999999998 0 999999999 999999999
2 999999998 3 999999999

output:

possible

result:

wrong answer 1st lines differ - expected: 'impossible', found: 'possible'