考虑怎样的点满足条件。设其为(xp,yp),则要满足(x0-xp,y0-yp)×(x1-xp,y1-yp)<=(xi-xp,yi-yp)×(xi+1-xp,yi+1-yp)对任意i成立。拆开式子,有(x0-xp)*(y1-yp)-(y0-yp)*(x1-xp)<=(xi-xp)*(yi+1-yp)-(yi-yp)*(xi+1-xp),也即x0y1-x0yp-xpy1-y0x1+y0xp+ypx1<=xiyi+1-xiyp-xpyi+1-yixi+1+yixp+ypxi+1。移项,得(y0-y1+yi+1-yi)xp+(x1-x0+xi-xi+1)yp<=xiyi+1-yixi+1-x0y1+y0x1。一长串乱七八糟的限制都是对(xp,yp)这个二元组的,半平面交即可。当然再套上一个凸包自身的限制。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 100010
#define vector point
#define double long double
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}
int gcd(int n,int m){return m==?n:gcd(m,n%m);}
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
const double eps=1E-;
struct point
{
double x,y;
vector operator +(const vector&a) const
{
return (vector){x+a.x,y+a.y};
}
vector operator -(const vector&a) const
{
return (vector){x-a.x,y-a.y};
}
double operator *(const vector&a) const
{
return x*a.y-y*a.x;
}
vector operator *(const double&a) const
{
return (vector){x*a,y*a};
}
}a[N];
struct line
{
point a;vector p;
bool operator <(const line&a) const
{
return atan2(p.x,p.y)>atan2(a.p.x,a.p.y);
}
}b[N<<];
int n,m,head,tail;
point p[N<<];
line q[N<<];
double area;
bool onright(point a,line p)
{
return (a-p.a)*p.p>=;
}
point cross(line a,line b)
{
return a.a+a.p*((b.p*(b.a-a.a))/(b.p*a.p));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj4445.in","r",stdin);
freopen("bzoj4445.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=;i<n;i++) a[i].x=read(),a[i].y=read();
for (int i=;i<n;i++) area+=a[i]*a[(i+)%n];
for (int i=;i<n;i++) m++,b[m].a=a[i],b[m].p=a[(i+)%n]-a[i];
for (int i=;i<n;i++)
{
double A=(a[].y-a[].y+a[(i+)%n].y-a[i].y),B=(a[].x-a[].x+a[i].x-a[(i+)%n].x),C=(a[i]*a[(i+)%n]-a[]*a[]);
m++;b[m].p=(vector){-B,A};
if (fabs(B)>0.5) b[m].a=(point){,C/B};
else b[m].a=(point){C/A,};
}
sort(b+,b+m+);
head=tail=;q[]=b[];
for (int i=;i<=m;i++)
{
while (head<tail&&onright(p[tail],b[i])) tail--;
while (head<tail&&onright(p[head+],b[i])) head++;
q[++tail]=b[i];
if (fabs(q[tail].p*q[tail-].p)<eps)
{
tail--;
if (onright(q[tail].a,b[i])) q[tail]=b[i];
}
if (head<tail) p[tail]=cross(q[tail],q[tail-]);
}
while (head<tail&&onright(p[tail],q[head])) tail--;
p[head]=cross(q[head],q[tail]);
double area2=;
for (int i=head;i<tail;i++)
area2+=p[i]*p[i+];area2+=p[tail]*p[head];
#undef double
printf("%.4f",(double)(area2/area));
return ;
}

最新文章

  1. [MySQL性能优化系列]提高缓存命中率
  2. 彻底理解session
  3. IOS-App installation failed原因及解决方法
  4. python问题:IndentationError:expected an indented block错误解决
  5. 结构类模式(三):组合(Composite)
  6. iOS中关于KVC与KVO知识点
  7. 一行代码搞定Adapter
  8. Installutil.exe 注册exe
  9. POJ 1700 经典过河问题(贪心)
  10. Smarty include
  11. MAC开发环境安装
  12. selenium python自动化简明演示
  13. C++多态及其实现原理
  14. 字符串匹配(二)----KMP算法
  15. xilinx Vivado的使用详细介绍(2):创建工程、添加文件、综合、实现、管脚约束、产生比特流文件、烧写程序、硬件验证
  16. LOJ500 ZQC的拼图 二分答案、DP
  17. 高可用Kubernetes集群-15. 部署Kubernetes集群统一日志管理
  18. Java Deadlock Example and How to analyze deadlock situation
  19. java类库 java API jar包 C语言函数库
  20. 通过python构建集中式的病毒扫描机制

热门文章

  1. Android学习之基础知识九 — 数据存储(持久化技术)之SQLite数据库存储
  2. 《MySQL必知必会》[04] 表的操作和视图的使用
  3. CF1105E Helping Hiasat 最大团
  4. React-理解Redux
  5. 调用不同目录类的protected构造器
  6. layer.conifrm 非阻塞执行 ztree删除节点 问题
  7. jackjson-databind-2.9.3 笔记
  8. doc窗口 输入命令net start mysql 服务名无效
  9. M2事后分析
  10. Week 1 工程表格