POJ 3410 Split convex polygon(凸包)
2024-10-07 07:41:32
题意是逆时针方向给你两个多边形,问你这两个多边形通过旋转和平移能否拼成一个凸包。
首先可以想到的便是枚举边,肯定是有一对长度相同的边贴合,那么我们就可以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 ;
}
最新文章
- [译]Modern Core Graphics with Swift系列
- inference和learning
- hdu 4045 2011北京赛区网络赛F 组合数+斯特林数 ***
- 深搜+回溯 POJ 2676 Sudoku
- C#线程 在某一时间内,只有N个线程在并发执行,其余都在队列中的实现(转载)
- POJ 1276 Cash Machine
- CSS最常用和实用的技巧
- 提问:";~";运算符
- HTML5小时钟
- 服务器编程入门(10)TCP回射服务器实现 - 并发
- Jquery 时间格式化
- ZOJ 2412 Farm Irrigation(DFS 条件通讯块)
- CentOS 7 时区设置
- Android开发8:数据存储(二)——SQLite数据库和ContentProvider的使用
- H5万能选择器:iosselect
- arm-linux-gcc: Command not found 问题解析 .
- [bzoj1901]动态区间k大
- 搞懂Redis RDB和AOF持久化及工作原理
- JSON 解析 (三)—— FastJSON与Jackson比较
- linux 创建用户和添加到组