QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201706 | #5151. Bottle Flip | SolitaryDream# | WA | 0ms | 11512kb | C++17 | 3.6kb | 2023-10-05 16:19:25 | 2023-10-05 16:19:25 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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