QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201968 | #5155. Faster Than Light | PlentyOfPenalty# | WA | 0ms | 3776kb | C++20 | 4.2kb | 2023-10-05 17:58:57 | 2023-10-05 17:58:58 |
Judging History
answer
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using V=long double;
const int N=2e5+9;
const V eps=(V)1e-7,T=10,L=1e9+T*T;
int n;
int sgn(V x){
if(fabsl(x)<eps)return 0;
return x<0?-1:1;
}
struct point{
V x,y;
friend V operator^(const point &a,const point &b){return a.x*b.y-a.y*b.x;}
friend V operator*(const point &a,const point &b){return a.x*b.x+a.y*b.y;}
friend inline point operator+(const point &a,const point &b){return {a.x+b.x,a.y+b.y};}
friend inline point operator-(const point &a,const point &b){return {a.x-b.x,a.y-b.y};}
};
struct line{
point s,e;
V angle;
line(){}
int x,y;
line(point s,point e,int _x=-1,int _y=-1):s(s),e(e){
x=_x,y=_y;
angle=atan2l(e.y-s.y,e.x-s.x);
}
inline bool operator<(const line &rhs)const{
return angle<rhs.angle;
}
point crosspoint(const line &v){
V a1=(v.e-v.s)^(s-v.s);
V a2=(v.e-v.s)^(e-v.s);
return point{
(s.x*a2-e.x*a1)/(a2-a1),
(s.y*a2-e.y*a1)/(a2-a1)
};
}
bool parallel(const line &v){
return sgn((e-s)^(v.e-v.s))==0;
}
};
struct rectangle{
int x1,y1,x2,y2;
}a[N];
void FOUND(){
cout<<"possible"<<endl;
exit(0);
}
struct halfplanes{
int n=0,st,ed;
vector<line> hp;
vector<point> p;
vector<int> que;
void push(const line &x){
if(hp.size()<n+5){
p.resize(n+5);
hp.resize(n+5);
que.resize(n+5);
}
hp[n++]=x;
}
void unique(){
int m=1;
for(int i=1;i<n;i++){
if(sgn(hp[i].angle-hp[i-1].angle)!=0){
hp[m++]=hp[i];
}else if(sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0){
hp[m-1]=hp[i];
}
}
n=m;
}
void debug(){
fprintf(stderr,"st=%d ed=%d\n",st,ed);
for(int i=st;i<=ed;i++)fprintf(stderr,"que[%d]=%d :: %d %d\n",i,que[i],hp[que[i]].x,hp[que[i]].y);
}
bool solve(){
sort(hp.begin(),hp.begin()+n);
// for(int i=0;i<n;i++)fprintf(stderr,"hp[%d]::%d %d::(%d,%d)->(%d,%d)\n",i,hp[i].x,hp[i].y,(int)hp[i].s.x,(int)hp[i].s.y,(int)hp[i].e.x,(int)hp[i].e.y);
unique();
que[st=0]=0;
que[ed=1]=1;
p[1]=hp[0].crosspoint(hp[1]);
for(int i=2;i<n;i++){
while(st<ed&&sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0)ed--;
while(st<ed&&sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0)st++;
que[++ed]=i;
if(hp[i].parallel(hp[que[ed-1]]))return false;
p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
// debug();
}
while(st<ed&&sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0)ed--;
while(st<ed&&sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0)st++;
// debug();
if(st+1>=ed)return false;
return true;
}
};
void check(){
halfplanes sol;
for(int i=1;i<=n;i++){
// fprintf(stderr,"a[%d] :: %d %d %d %d\n",i,a[i].x1,a[i].y1,a[i].x2,a[i].y2);
sol.push(line({1,(V)(a[i].y1-a[i].x1)},{0,(V)a[i].y1},i,1));
sol.push(line({0,(V)a[i].y2},{1,(V)(a[i].y2-a[i].x2)},i,2));
}
// sol.push(line({0,-T},{L,0}));
// sol.push(line({L-T,0},{L,L}));
// sol.push(line({L,L-T},{0,L}));
// sol.push(line({-T,L},{0,0}));
sol.push(line({-L,-L-T},{L,-L}));
sol.push(line({L-T,-L},{L,L}));
sol.push(line({L,L-T},{-L,L}));
sol.push(line({-L-T,L},{-L,-L}));
if(sol.solve())FOUND();
}
void basic_check(vector<pair<int,int>> &a){
vector<int> val;
for(auto &it:a){
val.push_back(it.first);
val.push_back(it.second);
}
sort(all(val));
val.erase(unique(all(val)),val.end());
vector<int> ins(val.size()),del(val.size());
for(auto &it:a){
it.first=lower_bound(all(val),it.first)-val.begin();
it.second=lower_bound(all(val),it.second)-val.begin();
ins[it.first]++;
del[it.second]++;
}
int cur=0;
for(int i=0;i<val.size();i++){
cur+=ins[i];
if(cur==n)FOUND();
cur-=del[i];
}
}
int main(){
#ifdef memset0
freopen("F.in","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
vector<pair<int,int>> allx,ally;
for(int i=1;i<=n;i++){
cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
// a[i].x1+=T>>1;
// a[i].y1+=T>>1;
// a[i].x2+=T>>1;
// a[i].y2+=T>>1;
allx.emplace_back(a[i].x1,a[i].x2);
ally.emplace_back(a[i].y1,a[i].y2);
swap(a[i].y1,a[i].y2);
}
basic_check(allx);
basic_check(ally);
check();
for(int i=1;i<=n;i++){
a[i].y1=1e9-a[i].y1;
a[i].y2=1e9-a[i].y2;
swap(a[i].y1,a[i].y2);
}
check();
cout<<"impossible"<<endl;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
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: 3620kb
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: 3624kb
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: 3776kb
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'