QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201890 | #5155. Faster Than Light | PlentyOfPenalty# | WA | 375ms | 121960kb | C++20 | 4.3kb | 2023-10-05 17:24:59 | 2023-10-05 17:24:59 |
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,T=10,L=1e9;
const V eps=1e-8;
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,"%d %d :: (%d,%d) -> (%d,%d)\n",i,1,1,a[i].y1-a[i].x1,0,a[i].y1);
// fprintf(stderr,"%d %d :: (%d,%d) -> (%d,%d)\n",i,2,0,a[i].y2,1,a[i].y2-a[i].x2);
// 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({-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].x1=/*1e9*/-a[i].x1;
a[i].x2=/*1e9*/-a[i].x2;
swap(a[i].y1,a[i].y2);
}
check();
cout<<"impossible"<<endl;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3700kb
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: 3664kb
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: 1ms
memory: 3664kb
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: 3828kb
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: 3832kb
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: 3924kb
input:
3 0 0 1 1000000000 2 0 999999999 1 2 999999999 999999999 1000000000
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
3 0 0 1 1000000000 2 0 999999999 1 2 999999999 1000000000 1000000000
output:
possible
result:
ok single line: 'possible'
Test #8:
score: 0
Accepted
time: 333ms
memory: 120044kb
input:
199999 433914929 216935871 433914930 216935872 621822279 310889546 621822280 310889547 395914333 197935573 395914334 197935574 582775641 291366227 582775642 291366228 658726133 329341473 658726134 329341474 71689261 35823037 71689262 35823038 453260967 226608890 453260968 226608891 249802825 1248798...
output:
impossible
result:
ok single line: 'impossible'
Test #9:
score: 0
Accepted
time: 331ms
memory: 120052kb
input:
199999 783545903 638444708 783545904 638444709 129510863 105527268 129510864 105527269 844145756 687822366 844145757 687822367 69111161 56312696 69111162 56312697 820438487 668505332 820438488 668505333 541037357 440845152 541037358 440845153 201057677 163824672 201057678 163824673 132372296 1078588...
output:
impossible
result:
ok single line: 'impossible'
Test #10:
score: 0
Accepted
time: 339ms
memory: 120016kb
input:
199999 90035476 60020102 90035477 60020103 482291029 321523804 482291030 321523805 943496815 628994328 943496816 628994329 278866936 185907742 278866937 185907743 310938589 207288844 310938590 207288845 203677765 135781628 203677766 135781629 368744134 245825874 368744135 245825875 559390024 3729231...
output:
impossible
result:
ok single line: 'impossible'
Test #11:
score: 0
Accepted
time: 348ms
memory: 120216kb
input:
199999 207687261 415417709 207687262 415417710 150460947 300965081 150460948 300965082 9349830 18742847 9349831 18742848 87879837 175802861 87879838 175802862 354035800 708114787 354035801 708114788 305159254 610361695 305159255 610361696 248609913 497263013 248609914 497263014 499646110 999335407 4...
output:
impossible
result:
ok single line: 'impossible'
Test #12:
score: 0
Accepted
time: 375ms
memory: 120320kb
input:
199999 79738802 97861382 79738803 97861383 614827422 754561052 614827423 754561053 517213290 634761890 517213291 634761891 788424494 967612004 788424495 967612005 613541698 752983118 613541699 752983119 698980304 857839589 698980305 857839590 487475098 598265018 487475099 598265019 733711836 9004646...
output:
impossible
result:
ok single line: 'impossible'
Test #13:
score: 0
Accepted
time: 344ms
memory: 121528kb
input:
199999 161399962 242105266 161399963 242105267 385751852 578633101 385751853 578633102 222705450 334063498 222705451 334063499 503730932 755601721 503730933 755601722 454037530 681061618 454037531 681061619 334605270 501913228 334605271 501913229 478675624 718018759 478675625 718018760 137316204 205...
output:
impossible
result:
ok single line: 'impossible'
Test #14:
score: 0
Accepted
time: 351ms
memory: 120436kb
input:
199999 222639792 110935680 222639793 110935683 931931336 465581452 931931337 465581455 35474718 17353143 35474719 17353146 206777070 103004319 206777071 103004322 914064786 456648177 914064787 456648180 301496196 150363882 301496197 150363885 515345552 257288560 515345553 257288563 500949336 2500904...
output:
impossible
result:
ok single line: 'impossible'
Test #15:
score: 0
Accepted
time: 337ms
memory: 121960kb
input:
199999 14166026 11542586 14166027 11542589 212205815 172908340 212205816 172908343 997392464 812690054 997392465 812690057 766610585 624645560 766610586 624645563 843092432 686964102 843092433 686964105 362333537 295234632 362333538 295234635 724513967 590344612 724513968 590344615 903878693 7364936...
output:
impossible
result:
ok single line: 'impossible'
Test #16:
score: 0
Accepted
time: 317ms
memory: 121788kb
input:
199999 259728590 173148768 259728591 173148771 221053226 147365192 221053227 147365195 899826680 599880828 899826681 599880831 847582532 565051396 847582533 565051399 258078974 172049024 258078975 172049027 369519293 246342570 369519294 246342573 214263539 142838734 214263540 142838737 737461550 491...
output:
impossible
result:
ok single line: 'impossible'
Test #17:
score: 0
Accepted
time: 334ms
memory: 120880kb
input:
199999 310634507 622037446 310634510 622037447 14947597 30663626 14947600 30663627 99728538 200225508 99728541 200225509 184650291 370069014 184650294 370069015 166422010 333612452 166422013 333612453 302228792 605226016 302228795 605226017 386996090 774760612 386996093 774760613 326681088 654130608...
output:
impossible
result:
ok single line: 'impossible'
Test #18:
score: 0
Accepted
time: 341ms
memory: 120832kb
input:
199999 799006978 980599598 799006981 980599599 101833006 124976996 101833009 124976997 491420512 603107117 491420515 603107118 529582438 649942208 529582441 649942209 453375406 556415396 453375409 556415397 591719612 726201467 591719615 726201468 775042202 951188282 775042205 951188283 218921560 268...
output:
impossible
result:
ok single line: 'impossible'
Test #19:
score: 0
Accepted
time: 325ms
memory: 120604kb
input:
199999 354595980 531899408 354595983 531899409 57294868 85947740 57294871 85947741 297914740 446877548 297914743 446877549 306592118 459893615 306592121 459893616 648745732 973124036 648745735 973124037 267426974 401145899 267426977 401145900 363073104 544615094 363073107 544615095 512209740 7683200...
output:
impossible
result:
ok single line: 'impossible'
Test #20:
score: -100
Wrong Answer
time: 343ms
memory: 121776kb
input:
200000 183486 13299 183487 13300 102571 78692 102572 78693 170699 23633 170700 23634 62500 111076 62501 111077 175314 19903 175315 19904 147075 42725 147076 42726 131050 55675 131051 55676 165234 28050 165235 28051 98541 81949 98542 81950 186747 10663 186748 10664 128558 57690 128559 57691 75090 100...
output:
impossible
result:
wrong answer 1st lines differ - expected: 'possible', found: 'impossible'