QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#142610 | #14. Breaking Bomber | NOI_AK_ME | 80 | 377ms | 241796kb | C++17 | 5.3kb | 2023-08-19 14:02:56 | 2023-08-19 14:02:57 |
Judging History
answer
#include<bits/stdc++.h>
#define Eps 1e-10
#define C_TYPE(X)const X&
#define FOR(i,l,r)for(int i=(l);i<=(r);i++)
#define AUTO(x,y)__typeof(y)x=y
#define FOR_EACH(x,v)for(AUTO(x,(v).begin());x!=(v).end();x++)
#define list vector
#define RAND(x)(rand()%(x))
using namespace std;struct Point{double x,y,z;Point(){}Point(double _x,double _y,double _z):x(_x),y(_y),z(_z){}};struct Face{Point normal;double c;Face(C_TYPE(Point)a,C_TYPE(Point)b,C_TYPE(Point)c);Face(){}};Point operator+(C_TYPE(Point)a,C_TYPE(Point)b){return Point(a.x+b.x,a.y+b.y,a.z+b.z);}Point operator-(C_TYPE(Point)a,C_TYPE(Point)b){return Point(a.x-b.x,a.y-b.y,a.z-b.z);}Point operator*(C_TYPE(Point)a,double b){return Point(a.x*b,a.y*b,a.z*b);}Point operator/(C_TYPE(Point)a,double b){return a*(1.0f/b);}double operator*(C_TYPE(Point)a,C_TYPE(Point)b){return a.x*b.x+a.y*b.y+a.z*b.z;}Point cross(C_TYPE(Point)a,C_TYPE(Point)b){return Point(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);}double mo2(C_TYPE(Point)a){return a.x*a.x+a.y*a.y+a.z*a.z;}double mo(C_TYPE(Point)a){return sqrt(mo2(a));}Point norm(C_TYPE(Point)a){return a/mo(a);}Face::Face(C_TYPE(Point)a,C_TYPE(Point)b,C_TYPE(Point)c):normal(norm(cross(b-a,c-a))),c(normal*a){}double faceDis(C_TYPE(Face)face,C_TYPE(Point)point){return face.normal*point-face.c;}bool seeFace(C_TYPE(Face)face,C_TYPE(Point)point){return faceDis(face,point)>-Eps;}Point faceToPoint(Face f,Point center){f.c-=f.normal*center;return f.normal/f.c;}struct CPoint;struct CFace;struct CLine;struct CPoint{Point p;list<CFace*>see;list<CFace*>made;};struct CLine{CFace*face;CPoint*point;CLine*back;CLine*next_line();};struct CFace{Face f;CPoint*killed;list<CPoint*>saw;CLine line[3];CFace(CPoint*p0,CPoint*p1,CPoint*p2):f(p0->p,p1->p,p2->p),killed(0){line[0]=(CLine){this,p1,0};line[1]=(CLine){this,p2,0};line[2]=(CLine){this,p0,0};}void setLineBack(CLine*l0,CLine*l1,CLine*l2){line[0].back=l0,l0->back=line+0;line[1].back=l1,l1->back=line+1;line[2].back=l2,l2->back=line+2;}void findSee(C_TYPE(list<CPoint*>)cd){FOR_EACH(cp,cd){if(*cp!=line[2].point&&seeFace(this->f,(*cp)->p)){saw.push_back((*cp));(*cp)->see.push_back(this);}}}void findSee(C_TYPE(list<CPoint*>)a,C_TYPE(list<CPoint*>)b){saw.resize(a.size()+b.size());saw.clear();AUTO(ia,a.begin());AUTO(ib,b.begin());CPoint*v_max=(CPoint*)-1;while(ia!=a.end()||ib!=b.end()){CPoint*va=(ia==a.end()?v_max:*ia);CPoint*vb=(ib==b.end()?v_max:*ib);ia+=(va<=vb);ib+=(vb<=va);CPoint*ck=min(va,vb);if(ck==line[2].point)continue;if(va==vb||seeFace(this->f,ck->p)){saw.push_back(ck);ck->see.push_back(this);}}}};CLine*CLine::next_line(){return this->face->line+2==this?this->face->line:this+1;}ostream&operator<<(ostream&cout,C_TYPE(Point)p){return cout<<"("<<p.x<<','<<p.y<<','<<p.z<<')';}ostream&operator<<(ostream&cout,C_TYPE(list<CPoint*>)p){cout<<'[';FOR_EACH(x,p)cout<<(*x)->p<<", ";cout<<']';}struct Hull3D{vector<CPoint>cp;vector<CPoint*>a;CPoint*root;int n;void initHull(CPoint*a,CPoint*b,CPoint*c);void insertPoint(CPoint*a);void clearAll();int inHull(Point p,CPoint*s);int inHull(Point p){return inHull(p,root);}void build(vector<Point>points);vector<Face>getAllFace();Point getCenter();};void Hull3D::initHull(CPoint*a,CPoint*b,CPoint*c){CFace*pf=new CFace(a,b,c);a->made.push_back(pf);CFace*pf2=new CFace(c,b,a);pf2->setLineBack(pf->line+1,pf->line+0,pf->line+2);a->made.push_back(pf2);list<CPoint*>all;FOR(i,0,n-1)if(&cp[i]!=this->a[0]&&&cp[i]!=this->a[1]&&&cp[i]!=this->a[2])all.push_back(&cp[i]);pf->findSee(all);pf2->findSee(all);}void Hull3D::insertPoint(CPoint*a){CLine*ps=0;FOR_EACH(f,a->see)if(!(*f)->killed){(*f)->killed=a;if(ps==0)FOR(i,0,2)if(!seeFace((*f)->line[i].back->face->f,a->p))ps=(*f)->line+i;}if(ps==0)return;CFace*pre=0;CLine*pt=ps;while(1){CFace*nf=new CFace(a,pt->back->point,pt->point);a->made.push_back(nf);nf->findSee(pt->face->saw,pt->back->face->saw);if(pre==0)nf->setLineBack(nf->line+2,pt->back,nf->line);else nf->setLineBack(pre->line+2,pt->back,pre->line[2].back);pre=nf;pt=pt->next_line();while(pt->back->face->killed)pt=pt->back->next_line();if(pt==ps)break;}}void Hull3D::clearAll(){FOR(i,0,n-1){cp[i].made.clear();cp[i].see.clear();}}int Hull3D::inHull(Point p,CPoint*s){FOR_EACH(i,s->made){if(faceDis((*i)->f,p)>Eps)if((*i)->killed)return inHull(p,(*i)->killed);else return 0;}return 1;}void Hull3D::build(vector<Point>points){n=points.size();cp.resize(n);a.resize(n);FOR(i,0,n-1){a[i]=&cp[i];swap(a[i],a[RAND(i+1)]);cp[i].p=points[i];}root=a[0];initHull(a[0],a[1],a[2]);FOR(i,3,n-1)insertPoint(a[i]);}vector<Face>Hull3D::getAllFace(){vector<Face>fs;for(auto&p:cp)for(auto&f:p.made)if(!f->killed)fs.push_back(f->f);return fs;}Point Hull3D::getCenter(){Point c(0,0,0);for(auto&p:cp)c=c+p.p;return c/cp.size();}int main(int argc,char**argv){srand(2333);int n;scanf("%d",&n);vector<Point>points;FOR(i,1,n){int x,y,z,p;scanf("%d%d%d%d",&x,&y,&z,&p);double s=x+y+z+p;points.push_back(Point(x/s,y/s,z/s));}Hull3D hull,hull2;hull.build(points);vector<Face>fs=hull.getAllFace();Point center=hull.getCenter();points.clear();for(auto&f:fs)points.push_back(faceToPoint(f,center));hull2.build(points);int q,i=0;scanf("%d",&q);while(i++,q--){int q;double a,b,c,d;scanf("%d%lf%lf%lf%lf",&q,&a,&b,&c,&d);int ans;if(q==1)ans=hull.inHull(Point(a,b,c)/(a+b+c+d));else{Face f;f.normal=Point(a-d,b-d,c-d);f.c=-d;if(!seeFace(f,center))ans=1-hull2.inHull(faceToPoint(f,center));else ans=1;}if(ans)printf("Y\n");else printf("N\n");}}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 3736kb
input:
10 0 0 0 1 1228 7353 6360 25059 5742 6557 4479 23222 8856 4182 337 26625 3034 8076 4648 24242 5098 6165 5659 23078 410 843 9754 28993 9171 427 3426 26976 5067 4817 6866 23250 5314 8100 1474 25112 10 1 1777 6559 5076 26588 2 52077995 121637995 47957995 -17962005 2 142988030 -74851970 213908030 -96011...
output:
Y Y N N N Y N N N N
result:
ok 10 lines
Test #2:
score: 10
Accepted
time: 2ms
memory: 4380kb
input:
100 0 0 0 1 6028 7649 1087 25236 7899 957 5720 25424 3859 8997 435 26709 2594 207 9448 27751 7808 4004 4363 23825 7863 5341 2380 24416 8367 4414 2557 24662 7334 5432 3568 23666 5196 7481 3614 23709 536 5410 8153 25901 6002 4191 6514 23293 5489 5611 5866 23034 6611 6252 3638 23499 5438 7912 1963 2468...
output:
N N N Y Y N N N N N N N N Y Y N N N N N N N Y Y N N N N N N N N N N Y Y N N N N Y Y N N N N N N N N N N N N N N N Y Y N N N N N N N N N N Y N N N N N N N N N N Y N N N Y N Y N N N Y N N N Y N N N N N
result:
ok 100 lines
Test #3:
score: 10
Accepted
time: 1ms
memory: 5200kb
input:
200 0 0 0 1 8962 264 3954 26820 8590 3390 3276 24744 6192 7583 431 25794 8543 4797 156 26504 3614 6872 5978 23536 5934 6976 3484 23606 7489 1932 6017 24562 3661 8088 4148 24103 1075 9046 3610 26269 9650 272 1683 28395 3884 83 8996 27037 6086 6887 3400 23627 6796 3069 6358 23777 1884 6433 7148 24535 ...
output:
N N N N Y N N N Y N Y N N N N N N Y N Y N N N N N N N Y N N N N N Y N N N N N N N N N N N N N N N N N N N N Y N N N N Y N Y N N N Y N N N N N N Y N N N N N N Y Y N Y N N N N N N N N N N N Y N N Y N Y Y N N N N Y N N N N Y N Y N N N N N N Y N Y N N N N Y N N N N N N N N N N N N N N Y N N Y Y N Y N Y ...
result:
ok 200 lines
Test #4:
score: 10
Accepted
time: 23ms
memory: 23608kb
input:
2000 0 0 0 1 6799 5772 4059 23370 8076 576 5520 25828 6728 4173 5774 23325 3165 7093 5975 23767 7975 3034 4818 24173 6193 5324 5415 23068 8742 2758 3462 25038 5285 8251 117 26347 5357 5824 5780 23039 6560 3300 6489 23651 5776 5768 5422 23034 7320 5155 3983 23542 5265 6714 4819 23202 4467 5310 6919 2...
output:
N N N N N N Y Y N Y Y N Y N N Y N Y N N N Y N Y Y Y N N N N N N Y Y Y N N N N N N N N Y N N Y Y N N N N Y N N N N N N N N N Y N N N Y N N Y N N N N N Y N N N N N N Y N Y N N N N N N Y N N N N Y N N Y Y N N Y Y Y N N N N Y N N N N Y N Y N N Y N N N N Y N Y N Y N N N N Y N N N N N N N N Y Y N Y N N Y ...
result:
ok 3000 lines
Test #5:
score: 10
Accepted
time: 50ms
memory: 44740kb
input:
4000 0 0 0 1 1644 6386 7249 24721 5601 8024 516 25859 8431 4778 1453 25338 4659 6552 5602 23187 3139 6742 6381 23738 4073 5380 7105 23442 5687 7366 3070 23877 6519 2795 6761 23925 6534 4794 5509 23163 3629 3431 8431 24509 6771 4444 5516 23269 810 8701 4434 26055 7174 575 6651 25600 5119 2745 7892 24...
output:
N Y Y N N N Y N N Y N N Y N N N N N Y N N Y Y Y N N N N N N Y N N Y N N Y Y Y Y N N Y Y N N N N N Y N Y N N N N Y N Y N N N Y N Y N Y N N N N N N N Y Y Y Y N Y Y N N Y N N Y Y N N N N Y Y N Y N N N Y N N N N N N N N N N N N N N N N Y N Y Y Y N Y Y Y N N N Y N Y N Y N Y N Y Y N N N N N Y Y N Y Y N Y ...
result:
ok 4000 lines
Test #6:
score: 10
Accepted
time: 138ms
memory: 104792kb
input:
10000 0 0 0 1 6220 6718 3495 23567 1516 5277 8117 25090 4010 4607 7662 23721 4782 3623 7748 23847 4924 6831 5012 23233 8733 4431 364 26472 4123 6963 5527 23387 5807 5356 5797 23040 7920 4743 3286 24051 1507 7232 6438 24823 8397 4022 3057 24524 6568 3603 6318 23511 5661 4412 6672 23255 4765 3166 7956...
output:
Y Y N N N Y Y N N Y N N N Y N Y Y N N N Y Y Y Y Y N N N N Y Y Y N Y N N Y N N N Y Y Y N N Y N N Y N Y Y N N N Y Y N Y Y Y N Y Y Y Y Y N N N N Y Y N Y N Y Y N N Y Y N Y Y N Y N N Y Y Y Y Y N N Y Y Y Y N N N N Y N N N Y N N N Y N N Y N N N Y Y Y Y N Y Y Y N Y Y N N N Y Y Y N Y N Y N Y Y N Y N Y Y N N ...
result:
ok 20000 lines
Test #7:
score: 10
Accepted
time: 267ms
memory: 181960kb
input:
20000 0 0 0 1 4930 6145 5827 23098 6965 5848 3649 23538 2204 6404 7082 24310 2205 5604 7730 24461 5069 8024 2438 24469 3547 7255 5551 23647 3869 8767 2047 25317 7273 6450 1235 25042 6368 884 7396 25352 6203 7585 132 26080 6815 5668 4178 23339 1820 3395 9010 25775 6522 7246 996 25236 8699 2356 3846 2...
output:
Y N N Y N N Y N N N Y N Y N Y N Y N N N Y Y N N Y Y N N N N Y N Y N N N Y N Y Y Y Y N N N Y Y Y Y Y N N Y N N N N Y Y N Y Y Y N N Y Y N Y N Y Y N Y N N Y N Y Y N Y N N N Y N Y Y N Y N Y N N Y Y N N N Y N Y Y Y N N Y N N N Y N N Y Y Y Y Y Y N N Y N N Y N Y Y N Y Y N N N N Y Y N N Y Y N Y N Y N N Y N ...
result:
ok 40000 lines
Test #8:
score: 10
Accepted
time: 377ms
memory: 241796kb
input:
30000 0 0 0 1 6144 1462 7493 24901 4973 8095 2402 24530 3408 8690 2984 24918 204 9757 885 29154 6105 5069 5749 23077 6109 3943 6570 23378 6543 7213 1088 25156 2820 9014 2610 25556 9030 3568 1326 26076 3953 1482 8843 25722 5277 5834 5844 23045 9009 3613 1343 26035 7655 5397 2882 24066 4869 6063 5962 ...
output:
N Y Y Y Y Y N N Y N Y N Y Y Y Y N Y N N Y Y Y N N N N N N Y N Y N Y Y N Y Y Y Y N N N N Y N N Y N N N Y N N Y Y N N N Y N Y Y N N N Y Y N N Y Y N N N Y Y Y N N Y N N N N N N Y N N N Y Y Y Y N N Y Y Y N Y N Y Y Y N Y Y N Y N N Y Y Y Y N N Y N Y Y Y Y N N N N N N N N Y Y Y Y Y N Y Y Y Y N N N N N N N ...
result:
ok 60000 lines
Test #9:
score: 0
Memory Limit Exceeded
input:
40000 0 0 0 1 7476 6158 1488 24878 9022 2028 3242 25708 7494 5799 2497 24210 6911 537 6926 25626 4082 2962 8401 24555 7225 4159 5151 23465 9229 3249 536 26986 6387 1663 7243 24707 7731 931 5949 25389 1923 8580 4325 25172 2400 5823 7507 24270 3302 1713 9066 25919 8619 3796 2708 24877 3813 7958 4262 2...
output:
result:
Test #10:
score: 0
Memory Limit Exceeded
input:
50000 0 0 0 1 7463 5508 3160 23869 9214 1682 2880 26224 6828 6180 3349 23643 4228 8519 2360 24893 7830 3266 4904 24000 3332 4278 8162 24228 6010 6034 4847 23109 6733 6826 2025 24416 7053 1244 6688 25015 7007 6801 823 25369 516 7045 6792 25647 8485 4447 2062 25006 6012 1691 7551 24746 1671 4805 8375 ...