【BZOJ4445】[Scoi2015]小凸想跑步

Description

小凸晚上喜欢到操场跑步,今天他跑完两圈之后,他玩起了这样一个游戏。
操场是个凸n边形,N个顶点按照逆时针从0~n-l编号。现在小凸随机站在操场中的某个位置,标记为P点。将P点与n个顶点各连一条边,形成N个三角形。如果这时P点,0号点,1号点形成的三角形的面积是N个三角形中最小的一个,小凸则认为这是一次正确站位。
现在小凸想知道他一次站位正确的概率是多少。

Input

第1行包含1个整数n,表示操场的顶点数和游戏的次数。
接下来有N行,每行包含2个整数Xi,Yi表示顶点的坐标。
输入保证按逆时针顺序输入点,所有点保证构成一个n多边形。所有点保证不存在三点共线。

Output

输出1个数,正确站位的概率,保留4位小数。

Sample Input

5
1 8
0 7
0 0
8 0
8 8

Sample Output

0.6316

HINT

3<=N<=10^5,-10^9<=X,Y<=10^9

题解:现在才发现,我有时喜欢用一条直线的左边来代表一个半平面,有时喜欢用一条直线的右面代表一个半平面。。不过无所谓啦~

题中的限制是三角形面积的大小关系,如果我们将三角形面积用叉积来表示的话很容易将所给条件变成n-1个不等式,外加n个不等式限定P在多边形内部。求半平面交即可。

至于精度。。。用long double,把eps删掉即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=200010;
typedef long double db;
struct point
{
db x,y;
point() {}
point(db a,db b) {x=a,y=b;}
point operator + (const point &a) const {return point(x+a.x,y+a.y);}
point operator - (const point &a) const {return point(x-a.x,y-a.y);}
point operator * (const db &a) const {return point(x*a,y*a);}
db operator * (const point &a) const {return x*a.y-y*a.x;}
}p[maxn];
struct line
{
point p,v;
db a;
line() {}
line(point x,point y) {p=x,v=y,a=atan2(v.y,v.x);}
}l[maxn];
int n,tot,h,t;
db ans,sum;
int q[maxn];
inline bool onlft(line a,point b)
{
return a.v*(b-a.p)>=0;
}
inline point getp(line a,line b)
{
point u=a.p-b.p;
db tmp=(b.v*u)/(a.v*b.v);
return a.p+a.v*tmp;
}
inline bool cmp(const line &a,const line &b)
{
if(fabs(a.a-b.a)==0) return onlft(a,b.p);
return a.a<b.a;
}
inline void HPI()
{
sort(l+1,l+tot+1,cmp);
int i,j=1;
for(i=2;i<=tot;i++) if(fabs(l[i].a-l[j].a)>0) l[++j]=l[i];
tot=j;
h=1,t=2,q[1]=1,q[2]=2;
for(i=3;i<=tot;i++)
{
while(h<t&&onlft(l[i],getp(l[q[t-1]],l[q[t]]))) t--;
while(h<t&&onlft(l[i],getp(l[q[h+1]],l[q[h]]))) h++;
q[++t]=i;
}
while(h<t&&onlft(l[q[h]],getp(l[q[t-1]],l[q[t]]))) t--;
for(i=h;i<t;i++) p[i]=getp(l[q[i]],l[q[i+1]]);
p[t]=getp(l[q[t]],l[q[h]]);
for(i=h;i<t;i++) ans+=p[i]*(p[i+1]-p[i]);
ans+=p[t]*(p[h]-p[t]);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd();
int i;
for(i=0;i<n;i++) p[i].x=rd(),p[i].y=rd();
p[n]=p[0];
for(i=0;i<n;i++) l[++tot]=line(p[i+1],p[i]-p[i+1]),sum+=p[i]*(p[i+1]-p[i]);
for(i=1;i<n;i++)
{
db a=p[i+1].x-p[i].x-p[1].x+p[0].x;
db b=p[i+1].y-p[i].y-p[1].y+p[0].y;
db c=-(p[i]*(p[i+1]-p[i]))+(p[0]*(p[1]-p[0]));
if(fabs(a)>0) l[++tot]=line(point(0,c/a),point(-a,-b));
else if(fabs(b)>0) l[++tot]=line(point(-c/b,0),point(0,-b));
}
HPI();
printf("%.4lf",(double)fabs(ans/sum));
return 0;
}

最新文章

  1. 深入理解java异常处理机制
  2. 无法定位序数4369于动态链接库libeay32.dll
  3. Android中取消GridView &amp; ListView默认的点击背景色
  4. EL表达式 (详解)
  5. Machine Learning - 第6周(Advice for Applying Machine Learning、Machine Learning System Design)
  6. python学习笔记(win32print API介绍)
  7. WeChat 6.3 wipe deleted chat messages as well as LINE 5.3 and above
  8. cdoj 1334 郭大侠与Rabi-Ribi 贪心+数据结构
  9. Linux 命令、Shell 杂货铺
  10. linux部署tomcat
  11. .NET单元测试艺术(2) - 第一个单元测试
  12. [Dev Blog] KCV插件 —— Provissy Tools 。
  13. Eclipse perl的IDE环境插件-EPIC
  14. css--position和float
  15. 【初码干货】关于.NET玩爬虫这些事
  16. 手机自动化测试:Appium源码分析之跟踪代码分析九
  17. MongoDB之基本操作与日常维护
  18. SQL数据库日志清理
  19. 5.21http网页基础
  20. MySQL导出TSV格式文件

热门文章

  1. 在web项目中集成pdf.js的默认查看器
  2. 禁止选中文本JS
  3. 4 云计算系列之Openstack简介与keystone安装
  4. 文件流方式 删除prefab空脚本
  5. Blender 移动、旋转、缩放
  6. 利用ROS工具从bag文件中提取图片
  7. 教你解锁被锁住的苹果mac电脑的文件跟文件夹,同时也可删除被锁的文件跟文件夹(转)
  8. 关于openssl的编译与使用
  9. 重新生成RF的测试库API文档
  10. 发送http请求