首页 > 代码库 > ZOJ 3495 Lego Bricks
ZOJ 3495 Lego Bricks
计算几何，暴力。
题目中有一句话：$The$ $mass$ $of$ $each$ $brick$ $is$ $equally$ $distributed$ $and$ $it$ $will$ $be$ $stable$ $if$ $it$ $is$ $placed$ $on$ $bases$ $or$ $stable$ $bricks$ $and$ $the$ $moment$ $of$ $it$ $can$ $be$ $zero$ $when$ $it$ $is$ $placed$.
核心原则：左右半段均有稳定的东西支撑，这条才算是稳定的。暴力扩展就可以了。需要用到判断线段不严格相交以及点到线段的最小距离。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0);void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}const double eps=1e-10;#define zero(x)(((x)>0?(x):(-x))<eps)struct point{ double x,y; point(double X,double Y) { x=X; y=Y; }};double xmult(point p1,point p2,point p0){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}int dots_inline(point p1,point p2,point p3){ return zero(xmult(p1,p2,p3));}int same_side(point p1,point p2,point l1,point l2){ return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;}int dot_online_in(point p,point l1,point l2){ return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;}int intersect_in(point u1,point u2,point v1,point v2){ if(!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2)) return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2); return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);}int T;struct YUAN{ double x,y,r;} yuan[200];struct XIAN{ double p1x,p1y,p2x,p2y;} xian[200];int n,m;int f[200];double DIS(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}point intersection(point u1,point u2,point v1,point v2){ point ret=u1; double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x)) /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x)); ret.x+=(u2.x-u1.x)*t; ret.y+=(u2.y-u1.y)*t; return ret;}point ptoseg(point p,point l1,point l2){ point t=p; t.x+=l1.y-l2.y,t.y+=l2.x-l1.x; if(xmult(l1,t,p)*xmult(l2,t,p)>eps) return DIS(p,l1)<DIS(p,l2)?l1:l2; return intersection(p,t,l1,l2);}int check(point A,point B,int b){ point F=ptoseg(point(yuan[b].x,yuan[b].y),A,B); double dis=DIS(F,point(yuan[b].x,yuan[b].y)); if(dis<=yuan[b].r) return 1; return 0;}int main(){ scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) scanf("%lf%lf%lf",&yuan[i].x,&yuan[i].y,&yuan[i].r); for(int i=1; i<=m; i++) scanf("%lf%lf%lf%lf",&xian[i].p1x,&xian[i].p1y,&xian[i].p2x,&xian[i].p2y); memset(f,0,sizeof f); int sum=0; while(1) { int Z=0; for(int i=1; i<=m; i++) { if(f[i]==1) continue; point p1= point(xian[i].p1x,xian[i].p1y); point p2= point(xian[i].p2x,xian[i].p2y); point p3= point((p1.x+p2.x)/2,(p1.y+p2.y)/2); int f1=0,f2=0; for(int j=1; j<=n; j++) { if(check(p1,p3,j)) f1=1; if(check(p2,p3,j)) f2=1; } for(int j=1; j<=m; j++) { if(f[j]==0) continue; if(intersect_in(p1,p3,point(xian[j].p1x,xian[j].p1y),point(xian[j].p2x,xian[j].p2y))) f1=1; if(intersect_in(p2,p3,point(xian[j].p1x,xian[j].p1y),point(xian[j].p2x,xian[j].p2y))) f2=1; } if(f1==1&&f2==1) f[i]=1,Z++; } if(Z==0) break; sum=sum+Z; } if(sum!=m) printf("NO\n"); else printf("YES\n"); } return 0;}
ZOJ 3495 Lego Bricks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。