肇庆市住房和城乡建设局网站,有人有片在线观看的资源,html界面设计工具,ui设计师导航网两个凸包判断经过旋转平移能否重合。 我一看。哇傻逼题十行秒掉。 交上去跑的飞快然后wa55。 。。。 然后这个题一共就55个点#xff0c;这网友的数据竟该死的强。 看了眼数据是两个反转的平行四边形#xff0c;再判下角度就好了。 怎么大家都在hash然后kmp啊。这好难啊。我根… 两个凸包判断经过旋转平移能否重合。 我一看。哇傻逼题十行秒掉。 交上去跑的飞快然后wa55。 。。。 然后这个题一共就55个点这网友的数据竟该死的强。 看了眼数据是两个反转的平行四边形再判下角度就好了。 怎么大家都在hash然后kmp啊。这好难啊。我根本不会这东西啊。。。 #include iostream
#include cstdio
#include algorithm
#include vector
#include cmath
#include deque
#include cstring#define rep(n) for(int i0;in;i)
using namespace std;
typedef double db;
const db eps1e-6;
const db piacos(-1);
int sign(db k){if (keps) return 1; else if (k-eps) return -1; return 0;
}
int cmp(db k1,db k2){return sign(k1-k2);}
struct point{db x,y;point operator (const point k1) const{return (point){k1.xx,k1.yy};}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};}bool operator (const point k1) const{int acmp(x,k1.x);if (a-1) return 1; else if (a1) return 0; else return cmp(y,k1.y)-1;}int operator (const point k1) const{return cmp(x,k1.x)0cmp(y,k1.y)0;}db abs(){return sqrt(x*xy*y);}db dis(point k1){return ((*this)-k1).abs();}int dis2(point k1){ return (dis(k1)*dis(k1));}point unit(){db wabs(); return point{x/w,y/w};}point turn90(){ return point{-y,x};}db getP()const { return sign(y)1||(sign(y)0sign(x)-1);}void print(){printf(%.11lf %.11lf\n,x,y);}
};
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.xk1.y*k2.y;}
db rad(point k1,point k2){ return atan2(cross(k1,k2),dot(k1,k2));}
int compareangle(point k1,point k2){return k1.getP()k2.getP()||(k1.getP()k2.getP()sign(cross(k1,k2))0);
}
point getLL(point k1,point k2,point k3,point k4){db w1cross(k1-k3,k4-k3),w2cross(k4-k3,k2-k3);return (k1*w2k2*w1)/(w1w2);
}
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];}line push(db eps){//向左手边平移eps//const db eps1e-6;point delta(p[1]-p[0]).turn90().unit()*eps;return {p[0]-delta,p[1]-delta};}
};
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));}
vectorpoint convexHull(vectorpointps){int n ps.size();if(n1)return ps;sort(ps.begin(),ps.end());vectorpoint qs(n*2);int k0;for(int i0;in;qs[k]ps[i])while (k1cross(qs[k-1]-qs[k-2],ps[i]-qs[k-2])0)--k;for(int in-2,tk;i0;qs[k]ps[i--])while (ktcross(qs[k-1]-qs[k-2],ps[i]-qs[k-2])0)--k;qs.resize(k-1);return qs;
}
vectorpoint a,b;
int n,m;point o1,o2;
int main(){scanf(%d%d,n,m);a.resize(n);b.resize(m);rep(n)scanf(%lf%lf,a[i].x,a[i].y);rep(m)scanf(%lf%lf,b[i].x,b[i].y);aconvexHull(a);bconvexHull(b);if(a.size()!b.size()){coutNOendl;return 0;}na.size();rep(n)o1o1a[i],o2o2b[i];o1o1/n;o2o2/n;rep(n)a[i]a[i]-o1;rep(n)b[i]b[i]-o2;sort(a.begin(),a.end(),compareangle);sort(b.begin(),b.end(),compareangle);rep(n){bool f1;db pre-1;for(int j0;jnf;j){if(cmp(a[j].abs(),b[(ij)%n].abs())!0)f0;db now rad(a[j],b[(ij)%n]);if(pre-1)prefabs(now);else if(cmp(fabs(now),pre))f0;}if(f){coutYESendl;return 0;}}coutNOendl;
} 转载于:https://www.cnblogs.com/MXang/p/11342570.html
