自己想了一个方法判断点是不是在凸包内,先求出凸包面积,在求由点与凸包上每两个点之间的面积(点已经排好序了),如果两者相等,则点在凸包内,否则不在(时间复杂度可能有点高)但是这题能过

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f; struct point{
double x,y;
};
point p[N],s[N][N];
int n,top[N];
bool vis[N];
inline bool zero(double x)
{
return fabs(x)<eps;
}
double dis(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double dir(point p1,point p2,point p3)
{
return (p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x);
}
bool comp(point p1,point p2)
{
double te=dir(p[],p1,p2);
if(te<)return ;
if(zero(te)&&dis(p[],p1)<dis(p[],p2))return ;
return ;
}
void Graham(int k)
{
int pos;
double minx=inf,miny=inf;
for(int i=;i<n;i++)
{
if(p[i].x<minx||(p[i].x==minx&&p[i].y<miny))
{
minx=p[i].x;
miny=p[i].y;
pos=i;
}
}
swap(p[],p[pos]);
sort(p+,p+n,comp);
p[n]=p[];
s[k][]=p[],s[k][]=p[], s[k][]=p[];
top[k]=;
for(int i=;i<=n;i++)
{
while(top[k]>=&&dir(s[k][top[k]-],s[k][top[k]],p[i])>=)top[k]--;
s[k][++top[k]]=p[i];
}
}
double square(int k)
{
double ans=;
for(int i=;i<top[k]-;i++)
ans-=dir(s[k][],s[k][i],s[k][i+]);
return ans/;
}
bool inside(double sq,double x,double y,int k)
{
double ans=;
point p0;p0.x=x,p0.y=y;
for(int i=;i<top[k];i++)
{
if(dir(p0,s[k][i],s[k][i+])<)ans-=dir(p0,s[k][i],s[k][i+]);
else ans+=dir(p0,s[k][i],s[k][i+]);
}
return sq*==ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int cnt=;
while(cin>>n,n!=-){
for(int i=;i<n;i++)
cin>>p[i].x>>p[i].y;
Graham(cnt);
cnt++;
}
/* for(int i=0;i<cnt;i++)
{
for(int j=0;j<top[i];j++)
cout<<s[i][j].x<<" "<<s[i][j].y<<endl;
}*/
memset(vis,,sizeof vis);
int x,y;
double ans=;
while(cin>>x>>y){
for(int i=;i<cnt;i++)
{
double sq=square(i);
if(!vis[i]&&inside(sq,x,y,i))
{
vis[i]=;
ans+=sq;
break;
}
}
}
cout<<setiosflags(ios::fixed)<<setprecision()<<ans<<endl;
return ;
}
/********************* *********************/

最新文章

  1. Windows+Caffe+VS2013+python接口配置过程
  2. nginx的日常应用
  3. Nancy之基于Nancy.Owin的小Demo
  4. 夺命雷公狗-----React---12--添加类和样式
  5. js兼容性记录
  6. 模拟Linux的shell
  7. embed 隐藏播放器显示
  8. 使用autolayout的NSLayoutConstraint类中的constraintWithItem 、constraintsWithVisualFormat这两个类方法来创建视图并可以实现自动布局
  9. 自定义sublime代码片段
  10. Ubuntu的默认root密码
  11. cannot find w3wp.exe in VS
  12. VS2012 直接浏览网页时报错
  13. 【2012.1.24更新】不要再在网上搜索eclipse的汉化包了!
  14. 调用支付宝接口Android客户端没有支付宝APP的情况下解决无法调用支付宝页面的问题
  15. 动态代理与AOP
  16. CodeForces 709C Letters Cyclic Shift
  17. jQuery Datetable
  18. [InstFiles]在Inno中打包隐藏和系统文件的头文件
  19. js点滴
  20. springBoot配置,贴个图

热门文章

  1. POJ1459:Power Network(dinic)
  2. Java Code Template
  3. spring mvc 全局处理异常
  4. Java数据结构——循环链表的实现
  5. Eclipse jvm启动参数在哪设置
  6. Hive环境安装
  7. NIO 03
  8. java中内存泄露和内存溢出
  9. java内存解析
  10. Junit中的setup和teardown方法