题意是逆时针方向给你两个多边形,问你这两个多边形通过旋转和平移能否拼成一个凸包。

首先可以想到的便是枚举边,肯定是有一对长度相同的边贴合,那么我们就可以n2枚举所有边对,接下来就是旋转点对,那么假设多边型在这条向量的左侧,那么我们可以根据叉积正负判断旋转的方向。

然后就是如何判断了,显然有一种情况是凸包里扣除整个多边形,那么这种情况我们需要对重合的边进行删除,可以发现,如果有重合的边,他一定是成对出现,有一条进去的边也有一条出来的边,那么我们可以直接通过vector不断插入的过程和之前那条边比较,是否是同一对点产生的边,如果是我们就直接抵消,进行下一次判断。

最后就是对这些绕着一圈的点进行判断是否是凸包,那么我们直接绕一圈判断两个向量叉积是否是小于0或者叉积等于0但是方向相反,那么这种情况也是非法。

还是有很多细节地方,此题好像eps要开大一点,不然会wa。


ans=

ans=
 //      ——By DD_BOND

 //#include<bits/stdc++.h>
//#include<unordered_map>
//#include<unordered_set>
#include<functional>
#include<algorithm>
#include<iostream>
//#include<ext/rope>
#include<iomanip>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<cstddef>
#include<cstdio>
#include<memory>
#include<vector>
#include<cctype>
#include<string>
#include<cmath>
#include<queue>
#include<deque>
#include<ctime>
#include<stack>
#include<map>
#include<set> #define fi first
#define se second
#define pb push_back
#define MP make_pair using namespace std; typedef double db;
typedef long ll;
typedef pair<db,db> Pd;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll; const db eps=1e-;
const int MAXN=1e3+;
const db pi=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3f; inline int dcmp(db x){
if(fabs(x)<eps) return ;
return (x>? : -);
} inline db Sqrt(db x){
return x>? sqrt(x): ;
} inline db sqr(db x){ return x*x; } struct Point{
db x,y;
Point(){ x=,y=; }
Point(db _x,db _y):x(_x),y(_y){}
void input(){
double _x,_y;
scanf("%lf%lf",&_x,&_y);
x=_x,y=_y;
}
bool operator ==(const Point &b)const{
return (dcmp(x-b.x)==&&dcmp(y-b.y)==);
}
bool operator <(const Point &b)const{
return (dcmp(x-b.x)==? dcmp(y-b.y)< : x<b.x);
}
Point operator +(const Point &b)const{
return Point(x+b.x,y+b.y);
}
Point operator -(const Point &b)const{
return Point(x-b.x,y-b.y);
}
Point operator *(db a){
return Point(x*a,y*a);
}
Point operator /(db a){
return Point(x/a,y/a);
}
db len2(){ //长度平方
return sqr(x)+sqr(y);
}
db len(){ //长度
return Sqrt(len2());
}
db polar(){ //向量的极角
return atan2(y,x); //返回与x轴正向夹角(-pi~pi]
}
Point change_len(db r){ //转化为长度为r的向量
db l=len();
if(dcmp(l)==) return *this; //零向量
return Point(x*r/l,y*r/l);
}
Point rotate(Point p,db ang){ //绕点p逆时针旋转ang度
Point v=(*this)-p;
db c=cos(ang),s=sin(ang);
return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
}
}; inline db cross(Point a,Point b){ //叉积
return a.x*b.y-a.y*b.x;
} inline db dot(Point a,Point b){ //点积
return a.x*b.x+a.y*b.y;
} inline db dis(Point a,Point b){ //两点的距离
Point p=b-a; return p.len();
} db rad(Point a,Point b){ //两个向量的夹角
return fabs(atan2(fabs(cross(a,b)),dot(a,b)));
} struct Node{
Point vec,s,t;
Node(){}
Node(Point a,Point b,Point c){
vec=a,s=b,t=c;
}
}; Point a[],b[],tmp[]; int main(void){
int n;
while(~scanf("%d",&n)){
int ans=;
for(int i=;i<n;i++) a[i].input(),a[i+n]=a[i];
int m; scanf("%d",&m);
for(int i=;i<m;i++) b[i].input(),b[i+m]=b[i]; for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(dcmp(dis(a[i],a[i+])-dis(b[j],b[j+]))==){
int p=,f=;
vector<Node>st;
db ang=rad(b[j+]-b[j],a[i+]-a[i]);
if(dcmp(cross(b[j+]-b[j],a[i+]-a[i]))>=) ang-=pi;
else ang=pi-ang; for(int k=;k<i;k++) tmp[p++]=a[k];
for(int k=j+;k<j+m+;k++) tmp[p++]=a[i+]+(b[k]-b[j]).rotate(Point(,),ang);
for(int k=i+;k<n;k++) tmp[p++]=a[k]; tmp[p]=tmp[]; for(int i=;i<p;i++){
Point res=tmp[i+]-tmp[i];
if(st.size()&&st.back().t==tmp[i]&&st.back().s==tmp[i+]) st.pop_back();
else st.pb(Node(res,tmp[i],tmp[i+]));
} st.pb(st[]);
for(int i=;i<(int)st.size();i++)
if(dcmp(cross(st[i-].vec,st[i].vec))<||
(dcmp(cross(st[i-].vec,st[i].vec))==&&dcmp(dot(st[i-].vec,st[i].vec))<=))
f=;
if(!f) ans=;
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. [译]Modern Core Graphics with Swift系列
  2. inference和learning
  3. hdu 4045 2011北京赛区网络赛F 组合数+斯特林数 ***
  4. 深搜+回溯 POJ 2676 Sudoku
  5. C#线程 在某一时间内,只有N个线程在并发执行,其余都在队列中的实现(转载)
  6. POJ 1276 Cash Machine
  7. CSS最常用和实用的技巧
  8. 提问:&quot;~&quot;运算符
  9. HTML5小时钟
  10. 服务器编程入门(10)TCP回射服务器实现 - 并发
  11. Jquery 时间格式化
  12. ZOJ 2412 Farm Irrigation(DFS 条件通讯块)
  13. CentOS 7 时区设置
  14. Android开发8:数据存储(二)——SQLite数据库和ContentProvider的使用
  15. H5万能选择器:iosselect
  16. arm-linux-gcc: Command not found 问题解析 .
  17. [bzoj1901]动态区间k大
  18. 搞懂Redis RDB和AOF持久化及工作原理
  19. JSON 解析 (三)—— FastJSON与Jackson比较
  20. linux 创建用户和添加到组

热门文章

  1. webpack--第三方loader
  2. mysql AUTO INCREMENT字段 语法
  3. python Tkinter 编程
  4. java总结2
  5. luogu P1314 聪明的质监员 x
  6. 【bzoj4562】[Haoi2016]食物链
  7. pyinstaller打包的exe太大?你需要嵌入式python玄学 探索篇
  8. (二)SQL -- 查询
  9. android网络连接工具类
  10. angular 的配置文件的应用