QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202395 | #5155. Faster Than Light | PhantomThreshold | WA | 0ms | 53988kb | C++14 | 7.3kb | 2023-10-06 00:23:37 | 2023-10-06 00:23:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//#define DEBUG
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;}
void print(){
cerr << (long long)p << "/" << (long long) q;
}
};
#ifdef DEBUG
typedef long double db;
#else
typedef frac db;
#endif
const db INF=1e9;
#ifdef DEBUG
const db eps=0;
#else
const db eps=0;
#endif
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);
}
#ifdef DEBUG
void print(){
cerr << "(" << x << "," << y << ") ";
}
#else
void print(){
cerr << "(";
x.print();
cerr << ",";
y.print();
cerr << ") ";
}
#endif
};
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];}
#ifdef DEBUG
void print(){
p[0].print();
cerr << "-> ";
p[1].print();
cerr << " ";
}
#else
void print(){
p[0].print();
cerr << "-> ";
p[1].print();
cerr << " ";
}
#endif
};
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));
// assert(sign(cross(k1.dir(),k2.dir()))!=0);
// assert(sign(cross(k1.dir(),k3.dir()))!=0);
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;
{
if (sign(cross(k1.dir(),k2.dir()))==0){
return sign(cross(k1[0]-k2[0],k2[1]-k2[0]))>=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);
}
{
if (sign(cross(k1.dir(),k3.dir()))==0){
return sign(cross(k1[0]-k3[0],k3[1]-k3[0]))>=0;
}
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);
}
if (flag) return rate1<=rate2;
else return rate1>=rate2;
}
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();
int pos=0,npos=1;
for (int i=0;i<sz;i++){
int nxt=(i+1)%sz;
if (!sameDir(L[i],L[nxt])){
pos=i;
npos=nxt;
}
}
for (int i=0;i<sz;i++){
if (i==pos || i==npos) continue;
if (!checkpos(L[pos],L[npos],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);
#ifdef DEBUG
cerr << "----------------" << endl;
for (auto l:L){
l.print();
cerr << endl;
}
#endif
L=getHL(L);
#ifdef DEBUG
cerr << "----------------" << endl;
for (auto l:L){
l.print();
cerr << endl;
}
#endif
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 53976kb
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: 53748kb
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: 53752kb
input:
3 1 1 2 2 1 3 2 4 3 3 4 4
output:
possible
result:
ok single line: 'possible'
Test #4:
score: 0
Accepted
time: 0ms
memory: 53672kb
input:
5 0 0 1 999999999 0 999999999 999999999 1000000000 1 0 999999998 1 999999998 0 999999999 999999999 2 999999998 3 999999999
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 0ms
memory: 53792kb
input:
4 0 1 1 1000000000 1 0 999999999 1 999999999 0 1000000000 999999999 2 999999999 999999999 1000000000
output:
possible
result:
ok single line: 'possible'
Test #6:
score: 0
Accepted
time: 0ms
memory: 53988kb
input:
3 0 0 1 1000000000 2 0 999999999 1 2 999999999 999999999 1000000000
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 53692kb
input:
3 0 0 1 1000000000 2 0 999999999 1 2 999999999 1000000000 1000000000
output:
impossible
result:
wrong answer 1st lines differ - expected: 'possible', found: 'impossible'