http://codeforces.com/gym/101484/problem/E

题解 凸包板题

#define _CRT_SECURE_NO_WARNINGS
#include<cmath>
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define rep(i,t,n) for(int i =(t);i<=(n);++i)
#define per(i,n,t) for(int i =(n);i>=(t);--i)
#define mmm(a,b) memset(a,b,sizeof(a)) const int maxn = 2e5 + ;
int a[maxn];
typedef long long ll;
const double eps = 1e-;//eps用于控制精度
struct Point//点或向量
{
double x, y;
Point() {}
Point(double x, double y) :x(x), y(y) {}
};
bool cmp1(Point a,Point b){
if(a.x==b.x)return a.y<b.y;
else return a.x<b.x;
}
struct triVec {
double x, y,z;
triVec() {}
triVec(double x, double y,double z) :x(x), y(y),z(z) {}
};
typedef Point Vector;
Vector operator + (Vector a, Vector b)//向量加法
{
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator - (Vector a, Vector b)//向量减法
{
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator * (Vector a, double p)//向量数乘
{
return Vector(a.x*p, a.y*p);
}
Vector operator / (Vector a, double p)//向量数除
{
return Vector(a.x / p, a.y / p);
}
int dcmp(double x)//精度三态函数(>0,<0,=0)
{
if (fabs(x) < eps)return ;
else if (x > )return ;
return -;
}
bool operator == (const Point &a, const Point &b)//向量相等
{
return dcmp(a.x - b.x) == && dcmp(a.y - b.y) == ;
}
double Dot(Vector a, Vector b)//内积
{
return a.x*b.x + a.y*b.y;
}
double Length(Vector a)//模
{
return sqrt(Dot(a, a));
}
Vector Rotate(Vector a, double rad)//逆时针旋转
{
return Vector(a.x*cos(rad) - a.y*sin(rad), a.x*sin(rad) + a.y*cos(rad));
}
double Cross(Vector a, Vector b)//外积
{
return a.x*b.y - a.y*b.x;
}
double Distance(Point a, Point b)//两点间距离
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
int n, m;
double z;
//Point p[maxn]; Point f1[maxn];
Point f2[maxn];
Point result[maxn];
vector<Point> P;
int top;
bool cmp(Point A, Point B)
{
double ans = Cross(A - P[], B - P[]);
if (dcmp(ans) == )
return dcmp(Distance(P[], A) - Distance(P[], B)) < ;
else
return ans > ;
}
void Graham()//Graham凸包扫描算法
{
for (int i = ; i < P.size(); i++)//寻找起点
if (P[i].y < P[].y || (dcmp(P[i].y - P[].y) == && P[i].x < P[].x))
swap(P[i], P[]);
sort(P.begin()+, P.end(), cmp);//极角排序,中心为起点
result[] = P[];
result[] = P[];
top = ;
for (int i = ; i < P.size(); i++)
{
while (Cross(result[top] - result[top - ], P[i] - result[top - ]) < && top >= )
top--;
result[++top] = P[i];
}
} int main() {
int n,m;
cin>>n>>m;
rep(i,,n){scanf("%lf%lf",&f1[i].x,&f1[i].y);P.push_back(f1[i]);}
rep(i,,m){scanf("%lf%lf",&f2[i].x,&f2[i].y);P.push_back(f2[i]);}
//if(n<=2||m<=2) return 0*printf("NO\n");
Graham();
sort(result,result+top,cmp);
sort(f1+,f1+n+,cmp);
sort(f2+,f2+n+,cmp);
int f=,ff=;
rep(i,,n){
if(!(f1[i]==result[i-]))f=; }
if(n!=top+)f=;
rep(i,,m){
if(!(f2[i]==result[i-]))ff=;
}
if(m!=top+)f=;
/* rep(i,1,n)cout<<f1[i].x<<'*'<<f1[i].y<<' ';
cout<<endl;
rep(i,1,m)cout<<f2[i].x<<'*'<<f2[i].y<<' ';
cout<<endl;
rep(i,0,top)cout<<result[i].x<<'*'<<result[i].y<<' ';
cout<<endl;*/
if(f|ff)puts("YES");
else puts("NO"); }

最新文章

  1. js前端实现模糊查询
  2. linux中解压缩并安装.tar.gz后缀的文件
  3. CRM 2013 安装前系统和数据库的基础配置
  4. shmget() -- 建立共享内存
  5. Android studio如何使用SVN进行版本控制?
  6. jstorm简介(转)
  7. JQuery 模糊匹配
  8. Mysql中常见索引操作
  9. appium 判断app是否安装
  10. API创建员工
  11. leetcode 104 Maximum Depth of Binary Tree二叉树求深度
  12. mysql-8.0.12-winx64 解压版安装(转)
  13. 微信小程序tabbar设置样式在哪里改
  14. tomcat 下配置 可 调试
  15. Zabbix 添加主机,获取模板templateID
  16. VS2010使用Release进行调试的三个必须设置选项
  17. RabbitMQ-官方指南-RabbitMQ配置
  18. ubuntu关闭防火墙
  19. java中boolean与字符串或者数字1和0的转换
  20. linux下apache的使用

热门文章

  1. Latex学习(一)
  2. Atitit.pagging &#160;翻页功能解决方案专题 与 目录大纲 v3 r44.docx
  3. pandas的qcut()方法
  4. Java如何进行Base64的编码(Encode)与解码(Decode)?
  5. chrome调试手机webview中页面
  6. CMake结合PCL库学习(3)
  7. Swagger使用小记
  8. java 全组合 与全排列
  9. 解决 Spring Oauth2 RedisTokenStore storeAccessToken 报错 java.lang.NoSuchMethodError: org.springframework.data.redis.connection.RedisConnection.set
  10. DrawerLayout 设置为滑动范围全盘