QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201706#5151. Bottle FlipSolitaryDream#WA 0ms11512kbC++173.6kb2023-10-05 16:19:252023-10-05 16:19:25

Judging History

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

  • [2023-10-05 16:19:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11512kb
  • [2023-10-05 16:19:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef double db;
const int N=2e5+50;
const db eps=1e-8;
int sgn(db x) {
    return x<-eps?-1:x>eps;
}
struct Point {
    db x,y;
    Point operator +(const Point &s) const{
        return {x+s.x,y+s.y};
    }
    Point operator -(const Point &s) const{
        return {x-s.x,y-s.y};
    }
    Point operator *(const db &s) const{
        return {x*s,y*s};
    }
};
db det(Point a,Point b) {
    return a.x*b.y-a.y*b.x;
}
bool Orient(Point a,Point b,Point c) {
    return sgn(det(b-a,c-a));
}
struct Line {
    Point u,v;
    double ang;
    Line(Point u_={0,0},Point v_={0,0}) {
        u=u_;
        v=v_;
        Point tmp=v-u;
        ang=atan2(tmp.y,tmp.x);
    }
    // bool operator <(const Line &s) const{
    //     return 
    // }
};
int GetInter(Line a,Line b,Point &rst) {
    db U=det(b.u-a.u,b.v-b.u);
    db D=det(a.v-a.u,b.v-b.u);
    if(!sgn(D)) return !sgn(U)?2:0;
    rst=a.u+(a.v-a.u)*(U/D);
    return 1;
}
bool Valid(Line a,Line b,Line w) {
    Point tmp;
    GetInter(a,b,tmp);
    return Orient(w.u,w.v,tmp)==1;
}
Line q[N];
bool half(vector<Line> l) {
    sort(l.begin(),l.end(),[&](auto &a,auto &b) {
        int d=sgn(a.ang-b.ang);
        return d?d==-1:Orient(a.u,a.v,b.u)<0;
    });
    int n=1;
    FOR(i,1,l.size()-1) {
        if(sgn(l[i].ang-l[i-1].ang))
            l[n++]=l[i];
    }
    l.resize(n);
    auto next=[&](int x){return x+1==n?0:x+1;};
    for(int i=0,tmp; i<n; ++i) {
        if((tmp=sgn(det(l[i].v-l[i].u,l[next(i)].v-l[next(i)].u)))<=0) {
            return 0;
        }
    }
    int h=0,t=0;
    q[t++]=l[0];
    q[t++]=l[1];
    for(int i=2; i<n; ++i) {
        while(t-h>=2 && !Valid(q[t-2],q[t-1],l[i])) --t;
        while(t-h>=2 && !Valid(q[h],q[h+1],l[i])) ++h;
        q[t++]=l[i];
        if(sgn(det(q[t-2].v-q[t-2].u,q[t-1].v-q[t-1].u))<=0) return 0;
    }
    while(t-h>=2 && !Valid(q[t-2],q[t-1],q[h])) --t;
    while(t-h>=2 && !Valid(q[h],q[h+1],q[t-1])) ++h;
    q[t]=q[h];
    // cerr << t << ' ' << h << endl;
    if(t-h<=1) return 0;
    return 1;
}
vector<Point> convex(vector<Point> a) {
    sort(a.begin(),a.end(),[](Point u,Point v) {
        return sgn(u.x-v.x)?u.x<v.x:u.y<v.y;
    });
    vector<Point> b;
    for(auto p: a) {
        while(b.size()>1 && sgn(det(b.back()-b[b.size()-2],p-b.back()))<=0) b.pop_back();
        b.push_back(p);
    }
    DOR(i,a.size()-2,0) {
        Point p=a[i];
        while(b.size()>1 && sgn(det(b.back()-b[b.size()-2],p-b.back()))<=0) b.pop_back();
        b.push_back(p);
    }
    b.pop_back();
    return b;
}
bool check(vector<Point> a,vector<Point> b) {
    vector<Line> l;
    FOR(i,0,a.size()-1) {
        int j=(i+1)%a.size();
        l.push_back(Line(a[i],a[j]));
    }
    FOR(i,0,b.size()-1) {
        int j=(i+1)%b.size();
        l.push_back(Line(b[i],b[j]));
    }
    return half(l);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Point> a[4];
    FOR(i,1,n) {
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        a[0].push_back((Point){(db)x1,(db)y1});
        a[1].push_back((Point){(db)x2,(db)y1});
        a[2].push_back((Point){(db)x2,(db)y2});
        a[3].push_back((Point){(db)x1,(db)y2});
    }
    FOR(i,0,3) a[i]=convex(a[i]);
    if(check(a[0],a[2]) && check(a[1],a[3])) {
        cout << "impossible\n";
    } else {
        cout << "possible\n";
    }
    return 0;
}

详细

Test #1:

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

input:

22 4 1 4

output:

possible

result:

wrong output format Expected double, but "possible" found