http://acm.sgu.ru/problem.php?contest=0&problem=253

题意简单易懂...给你n个点的凸包(经测试已经是极角序)...判断m个点是否在凸包内...数量>=k就输出YES

46ms过的...貌似数据很水...但暴力判断每个点复杂度O(n*m)肯定T了...

二分可以优化到O(mlogn)   -----该算法受到AC巨巨的启发:http://hi.baidu.com/aekdycoin/item/2d54f9c0fef55457ad00efd6

把凸包分成n-2个三角形...然后二分点是否在这些三角形内即可...注意一下只有三个点的情况即可

/********************* Template ************************/
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std; #define EPS 1e-8
#define MAXN 100005
#define MOD (int)1e9+7
#define PI acos(-1.0)
#define INF ((1LL)<<50)
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define BUG cout<<"BUG! "<<endl
#define LINE cout<<"------------------"<<endl
#define L(t) (t << 1)
#define R(t) (t << 1 | 1)
#define Mid(a,b) ((a + b) >> 1)
#define lowbit(a) (a & -a)
#define FIN freopen("in.txt","r",stdin)
#pragma comment (linker,"/STACK:102400000,102400000") // typedef long long LL;
// typedef unsigned long long ULL;
// typedef __int64 LL;
// typedef unisigned __int64 ULL;
// int gcd(int a,int b){ return b?gcd(b,a%b):a; }
// int lcm(int a,int b){ return a*b/gcd(a,b); } /********************* F ************************/
struct POINT{
double x,y;
POINT(double _x = , double _y = ):x(_x),y(_y){};
void show(){
cout<<x<<" "<<y<<endl;
}
};
POINT p[MAXN],wp[MAXN];
double multiply(POINT sp,POINT ep,POINT op){ //叉积
return (sp.x-op.x) * (ep.y-op.y) - (ep.x-op.x) * (sp.y-op.y);
}
bool onseg(POINT a,POINT s,POINT e){ // 判断点是否在线段上
if(multiply(a,s,e) == && a.x <= max(s.x,e.x) && a.x >= min(s.x,e.x)
&& a.y <= max(s.y,e.y) && a.y >= min(s.y,e.y))
return true;
return false;
}
bool inside(POINT pp,POINT sp,POINT ep,POINT op){ //判断点pp是否在三角形中(极角序)
if(onseg(pp,sp,ep) || onseg(pp,sp,op) || onseg(pp,ep,op)) //如果在三角形上
return true;
if(multiply(sp,ep,pp) > && multiply(ep,op,pp) >
&& multiply(sp,op,pp) < ) //如果在三角形内
return true;
return false;
}
bool bsearch(POINT a,int len){ //二分所构造的三角形
int l = ,r = len,m;
while(l < r){
m = (l + r) / ;
if(inside(a,p[],p[m],p[m+]) == true) return true;
if(multiply(p[],p[m],a) >= && multiply(p[],p[m+],a) <=
&& multiply(p[m],p[m+],a) < ) return false;
if(multiply(p[],p[m],a) > && multiply(p[],p[m+],a) > )
l = m + ;
else r = m;
}
return false;
}
int main()
{
//freopen("in.txt","r",stdin);
int n,m,k,tmp = ,cnt = ;
scanf("%d%d%d",&n,&m,&k);
for(int i = ; i < n ; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
p[n] = p[];
for(int i = ; i < m ; i++){
scanf("%lf%lf",&wp[i].x,&wp[i].y);
if(bsearch(wp[i],n-) == true) cnt++;
}
if(cnt >= k) printf("YES\n");
else printf("NO\n");
return ;
}

最新文章

  1. SQL添加维护 计划失败
  2. 字符编码笔记:ASCII,Unicode和UTF-8 转
  3. XidianOJ 1154 Nhywieza 的串
  4. 微信公众账号开发之N个坑(一)
  5. 【126】win8的一些问题
  6. Linux 命令 - at: 在指定的时间执行任务
  7. struts2-权限拦截器、日志拦截器、execAndWait(进度条)拦截器配置
  8. golang-mongodb范例
  9. 对于用div+css随心所欲布局的思考
  10. 面向面试编程——javascript对象的几种创建方式
  11. JavaScript基础:BOM的常见内置方法和内置对象
  12. PACKAGE-INFO.JAVA 作用及用法详解
  13. linux 配置vim(vimrc)
  14. 【PAT】B1079 延迟的回文数(20 分)
  15. Linux使用退格键时出现^H解决方法
  16. @EnableConfigurationProperties、@EnableAsync、 @EnableTransactionManagement
  17. Python学习笔记之在Python中实现单例模式
  18. django中对数据库的增删改查
  19. Java容器深入浅出之String、StringBuffer、StringBuilder
  20. CSS中的EM属性之弹性布局

热门文章

  1. uvalive 4730王国kingdom(并查集+线段树)
  2. SpringMVC 常见异常处理
  3. 静态时序分析SAT
  4. scikit-learn 为机器学习
  5. 解决Maven项目相互依赖/循环依赖/双向依赖的问题
  6. 【实用篇】获取Android通讯录中联系人信息
  7. web.config添加identity impersonate=&quot;true&quot;导致拒绝访问
  8. ping 原理及ICMP协议简介
  9. 页面打开pdf格式文件的方法
  10. 使程序在Linux下后台运行 (关掉终端继续让程序运行的方法)