半平面交,二分;

注意,题目的点是顺时针给出的;

 #include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 50010
#define eps 1e-6
using namespace std; int dcmp(double x)
{
return fabs(x) < eps ? : (x > ? : -);
} struct Point
{
double x;
double y;
Point(double x = , double y = ):x(x), y(y) {}
};
typedef Point Vector; Vector operator + (Point A, Point B)
{
return Vector(A.x + B.x, A.y + B.y);
} Vector operator - (Point A, Point B)
{
return Vector(A.x - B.x, A.y - B.y);
} Vector operator * (Point A, double p)
{
return Vector(A.x * p, A.y * p);
} Vector operator / (Point A, double p)
{
return Vector(A.x / p, A.y / p);
}
double dot(Point a,Point b)
{
return a.x*b.x+a.y*b.y;
}
double cross(Point a,Point b)
{
return a.x*b.y-a.y*b.x;
} Vector nomal(Vector a)
{
double l=sqrt(dot(a,a));
return Vector(-a.y/l,a.x/l);
} struct line
{
Point p;
Vector v;
double ang;
line() {}
line(Point p,Vector v):p(p),v(v)
{
ang=atan2(v.y,v.x);
}
bool operator<(const line &t)const
{
return ang<t.ang;
}
}; bool onleft(line l,Point p)
{
return (cross(l.v,p-l.p)>);
} Point getintersection(line a,line b)
{
Vector u=a.p-b.p;
double t=cross(b.v,u)/cross(a.v,b.v);
return a.p+a.v*t;
} int halfplanintersection(line *l,int n,Point *poly)
{
sort(l,l+n);
int first,last;
Point *p=new Point[n];
line *q=new line[n];
q[first=last=]=l[];
for(int i=; i<n; i++)
{
while(first<last && !onleft(l[i],p[last-]))last--;
while(first<last && !onleft(l[i],p[first]))first++;
q[++last]=l[i];
if(fabs(cross(q[last].v,q[last-].v))<eps)
{
last--;
if(onleft(q[last],l[i].p))q[last]=l[i];
}
if(first<last)p[last-]=getintersection(q[last-],q[last]);
}
while(first<last && !onleft(q[first],p[last-]))last--;
if((last-first )<=)return ;
p[last]=getintersection(q[last],q[first]);
int m=;
for(int i=first; i<=last; i++)poly[m++]=p[i];
return m;
} Point p[maxn],poly[maxn],v[maxn];
line l[maxn]; int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=;i<=n/;i++) swap(p[i],p[n-i]);
int left=,right=n-;
int ans;
while(left<=right)
{
int mid=(left+right)>>;
for(int i=;i<n;i++)
{
v[i]=p[(i+mid+)%n]-p[i];
l[i]=line(p[i],v[i]);
}
int m=halfplanintersection(l,n,poly);
if(!m){ans=mid;right=mid-;}
else left=mid+;
}
printf("%d\n",ans);
}
}

最新文章

  1. excel导出
  2. 【转】webGL与OpenGL的不同
  3. php solr 扩展
  4. 《Nagios系统监控实践》一书出版
  5. 判断是否为ie(包含ie11)
  6. 关于C语言中用Keil软件制作Lib库文件的几点经验
  7. 20170717_python_爬虫_网页数据解析_BeautifulSoup_数据保存_pymysql
  8. Java框架之Mybatis(一)
  9. 05_Python Format Operation
  10. C++并发编程学习笔记
  11. Tomcat异常及解决办法——持续更新中
  12. String.split()与StringUtils.split()
  13. Win10系统截屏快捷键
  14. 如何使用require.js?
  15. Linux内核第八节 20135332武西垚
  16. 神经网络优化算法如何选择Adam,SGD
  17. Vue学习二:v-model指令使用方法
  18. 二分法检索(binary search)(又名二进制搜索)
  19. java Field 二三事
  20. JavaScript中的垃圾回收机制与内存泄露

热门文章

  1. 昨天冲动的搬到外面住了,oh yeah
  2. Office365 InfoPath 表单的设计和应用(原创)
  3. CSS常用布局实现方法
  4. c# 远程监控(1) 大纲
  5. QL Server 中四种匹配符的含义
  6. jquery之each
  7. Java的基本数据类型
  8. [leetcode] 403. Frog Jump
  9. 空对象模式(Null Object Pattern)
  10. outlet删除不完全