uva 1475 - Jungle Outpost
2024-10-14 09:38:14
半平面交,二分;
注意,题目的点是顺时针给出的;
#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);
}
}
最新文章
- excel导出
- 【转】webGL与OpenGL的不同
- php solr 扩展
- 《Nagios系统监控实践》一书出版
- 判断是否为ie(包含ie11)
- 关于C语言中用Keil软件制作Lib库文件的几点经验
- 20170717_python_爬虫_网页数据解析_BeautifulSoup_数据保存_pymysql
- Java框架之Mybatis(一)
- 05_Python Format Operation
- C++并发编程学习笔记
- Tomcat异常及解决办法——持续更新中
- String.split()与StringUtils.split()
- Win10系统截屏快捷键
- 如何使用require.js?
- Linux内核第八节 20135332武西垚
- 神经网络优化算法如何选择Adam,SGD
- Vue学习二:v-model指令使用方法
- 二分法检索(binary search)(又名二进制搜索)
- java Field 二三事
- JavaScript中的垃圾回收机制与内存泄露