QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#202375 | #5155. Faster Than Light | PhantomThreshold | WA | 1ms | 5816kb | C++14 | 6.4kb | 2023-10-05 23:46:10 | 2023-10-05 23:46:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
struct frac{
ll p,q;
inline frac(){p=0;q=1;}
inline frac(ll x){p=x,q=1;}
inline frac(ll x,ll y){ll d=__gcd(x,y);p=x/d,q=y/d;if(q<0) p=-p,q=-q;}
inline frac operator + (const frac &x) const{return frac(p*x.q+q*x.p,q*x.q);}
inline frac operator - (const frac &x) const{return frac(p*x.q-q*x.p,q*x.q);}
inline frac operator - () const{return frac(-p,q);}
inline frac operator * (const frac &x) const{return frac(p*x.p,q*x.q);}
inline frac operator / (const frac &x) const{return frac(p*x.q,q*x.p);}
inline bool operator < (const frac &x) const{return p*x.q<q*x.p;}
inline bool operator <= (const frac &x) const{return p*x.q<=q*x.p;}
inline bool operator == (const frac &x) const{return p*x.q==q*x.p;}
inline bool operator > (const frac &x) const{return p*x.q>q*x.p;}
inline bool operator >= (const frac &x) const{return p*x.q>=q*x.p;}
inline bool operator != (const frac &x) const{return p*x.q!=q*x.p;}
};
typedef long double db;
const db INF=1e9;
const db eps=1e-7;
int sign(db k){
if (k>eps) return 1;
else if (k<-eps) return -1;
return 0;
}
int cmp(db k1,db k2){return sign(k1-k2);}
int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}
struct point{
db x,y;
point operator + (const point &k1) const{return (point){x+k1.x,y+k1.y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
point operator / (db k1) const{return (point){x/k1,y/k1};}
int operator == (const point &k1) const{return cmp(x,k1.x)==0 && cmp(y,k1.y)==0;}
point turn90(){
return (point){-y,x};
}
db abs2(){
return x*x+y*y;
}
int getP() const{
return sign(y)==-1 || (sign(y)==0 && sign(x)==-1);
}
/*
void print(){
cerr << "(" << x << "," << y << ") ";
}
*/
};
db cross(point k1,point k2){
return k1.x*k2.y-k1.y*k2.x;
}
db dot(point k1,point k2){
return k1.x*k2.x+k1.y*k2.y;
}
int compareangle(point k1,point k2){
return k1.getP()<k2.getP() || (k1.getP()==k2.getP() && sign(cross(k1,k2))>0);
}
point proj(point k1,point k2,point q){
point k=k2-k1;
return k1+k*(dot(q-k1,k)/k.abs2());
}
int checkLL(point k1,point k2,point k3,point k4){
return cmp(cross(k3-k1,k4-k1),cross(k3-k2,k4-k2))!=0;
}
point getLL(point k1,point k2,point k3,point k4){
db w1=cross(k1-k3,k4-k3);
db w2=cross(k4-k3,k2-k3);
return (k1*w2+k2*w1)/(w1+w2);
}
struct line{
point p[2];
line(point k1,point k2){p[0]=k1;p[1]=k2;}
point& operator [](int k){return p[k];}
int include(point k){return sign(cross(p[1]-p[0],k-p[0]))>=0;}
point dir(){return p[1]-p[0];}
/*
void print(){
p[0].print();
cerr << "-> ";
p[1].print();
cerr << " ";
}
*/
};
point getLL(line k1,line k2){return getLL(k1[0],k1[1],k2[0],k2[1]);}
int parallel(line k1,line k2){return sign(cross(k1.dir(),k2.dir()))==0;}
int sameDir(line k1,line k2){
return parallel(k1,k2) && sign(dot(k1.dir(),k2.dir()))==1;
}
int operator < (line k1,line k2){
if (sameDir(k1,k2)) return k2.include(k1[0]);
return compareangle(k1.dir(),k2.dir());
}
int checkpos(line k1,line k2,line k3){
return k3.include(getLL(k1,k2));
if (sign(cross(k1.dir(),k2.dir()))<0) swap(k1,k2);
bool flag=sign(cross(k1.dir(),k3.dir()))<0;
db rate1=0,rate2=0;
{
db w1=cross(k1[0]-k2[0],k2[1]-k2[0]);
db w2=cross(k2[1]-k2[0],k1[1]-k2[0]);
rate1=w1/(w1+w2);
}
{
db w1=cross(k1[0]-k3[0],k3[1]-k3[0]);
db w2=cross(k3[1]-k3[0],k1[1]-k3[0]);
rate2=w1/(w1+w2);
}
return (rate1<=rate2)^flag;
}
vector<line> getHL(vector<line> &L){
sort(L.begin(),L.end());
deque<line> q;
for (int i=0;i<(int)L.size();i++){
if (i && sameDir(L[i],L[i-1])) continue;
while (q.size()>1 && !checkpos(q[q.size()-2],q[q.size()-1],L[i])) q.pop_back();
while (q.size()>1 && !checkpos(q[1],q[0],L[i])) q.pop_front();
q.push_back(L[i]);
}
while (q.size()>2 && !checkpos(q[q.size()-2],q[q.size()-1],q[0])) q.pop_back();
while (q.size()>2 && !checkpos(q[1],q[0],q[q.size()-1])) q.pop_front();
vector<line> ans;
for (int i=0;i<(int)q.size();i++) ans.push_back(q[i]);
return ans;
}
const int maxn=400000;
int n;
point a[maxn+50];
point b[maxn+50];
void gao1(vector<line> &L,db x,db y){
point P=(point){0,y};
point Q=(point){1,y-x};
point R=P+(Q-P).turn90();
if (R.x*x+R.y>y) swap(P,Q);
L.emplace_back(P,Q);
}
void gao2(vector<line> &L,db x,db y){
point P=(point){0,y};
point Q=(point){1,y-x};
point R=P+(Q-P).turn90();
if (R.x*x+R.y<y) swap(P,Q);
L.emplace_back(P,Q);
}
bool checkXY(vector<pair<int,int>> &v){
int sz=v.size();
sort(v.begin(),v.end(),
[&](const pair<int,int> &A,const pair<int,int> &B){
return A.second<B.second;
}
);
int mxl=-1e9;
for (int i=0;i<sz;i++) mxl=max(mxl,v[i].first);
if (mxl<=v[0].second) return true;
return false;
}
bool checkOK(vector<line> &L){
if (L.size()<=2) return false;
int sz=L.size();
for (int i=2;i<sz;i++){
if (!checkpos(L[0],L[1],L[i])) return false;
}
return true;
}
int main(){
ios_base::sync_with_stdio(false);
vector<pair<int,int>> vx;
vector<pair<int,int>> vy;
cin >> n;
for (int i=1;i<=n;i++){
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
a[i]=(point){db(x1),db(y1)};
b[i]=(point){db(x2),db(y2)};
vx.emplace_back(x1,x2);
vy.emplace_back(y1,y2);
}
if (checkXY(vx) || checkXY(vy)){
cout << "possible" << "\n";
return 0;
}
{
vector<line> L;
L.emplace_back((point){db(0),db(1)},(point){db(0),db(0)});
L.emplace_back((point){db(INF),db(0)},(point){db(INF),db(1)});
for (int i=1;i<=n;i++){
gao1(L,a[i].x,b[i].y);
gao2(L,b[i].x,a[i].y);
}
gao1(L,0,INF);
gao2(L,INF,0);
/*
cerr << "----------------" << endl;
for (auto l:L){
l.print();
cerr << endl;
}
*/
L=getHL(L);
/*
cerr << "----------------" << endl;
for (auto l:L){
l.print();
cerr << endl;
}
*/
if (checkOK(L)){
cout << "possible" << "\n";
return 0;
}
}
{
vector<line> L;
L.emplace_back((point){db(0),db(0)},(point){db(0),db(1)});
L.emplace_back((point){db(-INF),db(1)},(point){db(-INF),db(0)});
for (int i=1;i<=n;i++){
gao1(L,b[i].x,b[i].y);
gao2(L,a[i].x,a[i].y);
}
gao1(L,INF,INF);
gao2(L,0,0);
L=getHL(L);
if (checkOK(L)){
cout << "possible" << "\n";
return 0;
}
}
cout << "impossible" << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5704kb
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: 0ms
memory: 5816kb
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: 0ms
memory: 5664kb
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: 1ms
memory: 5684kb
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'