先求半平面交,然后建塔的地方肯定是在半平面交的交点上或者是在地面线段的交点上。

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cctype>
#define rep(i, l, r) for(int i=l; i<=r; i++)
#define maxn 1009
#define linf 1e15
using namespace std;
inline int read()
{
int x=0, f=1; char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while (isdigit(ch)) x=x*10+ch-'0', ch=getchar();
return x*f;
}
struct P{double x, y;} p[maxn], p2[maxn];
struct line{P a, b; double ang;} g[maxn], l[maxn], a[maxn], q[maxn];
P operator - (P a, P b){return (P){a.x-b.x, a.y-b.y};}
double operator * (P a, P b){return a.x*b.y-a.y*b.x;}
bool operator < (line a, line b){if (a.ang==b.ang) return (a.b-a.a)*(b.a-a.a)>0; return a.ang<b.ang;}
bool operator < (P a, P b){return a.x<b.x;}
inline P inter(line a, line b)
{
double k1=(b.b-a.a)*(a.b-a.a), k2=(a.b-a.a)*(b.a-a.a), t=k2/(k1+k2);
return (P){b.a.x+t*(b.b.x-b.a.x), b.a.y+t*(b.b.y-b.a.y)};
}
inline bool jud(line a, line b, line v){return (inter(a, b)-v.a)*(v.b-v.a)>0;} int n, m, L, R, cnt;
double ans;
int main()
{
n=read(); m=n-1;
rep(i, 1, n) p[i].x=read();
rep(i, 1, n) p[i].y=read();
rep(i, 1, m) g[i].a=p[i], g[i].b=p[i+1];
rep(i, 1, m) l[i]=g[i], l[i].ang=atan2(l[i].b.y-l[i].a.y, l[i].b.x-l[i].a.x);
sort(l+1, l+m+1);
a[++cnt]=l[1]; rep(i, 2, m) a[a[cnt].ang!=l[i].ang ? ++cnt : cnt]=l[i];
L=1, R=0, q[++R]=a[1], q[++R]=a[2];
rep(i, 3, cnt)
{
while (L<R && jud(q[R-1], q[R], a[i])) R--;
while (L<R && jud(q[L+1], q[L], a[i])) L++;
q[++R]=a[i];
}
while (L<R && jud(q[R-1], q[R], q[L])) R--;
while (L<R && jud(q[L+1], q[L], q[R])) L++;
rep(i, L, R-1)
{
p2[i]=inter(q[i], q[i+1]);
if (p2[i].x>=p[1].x && p2[i].x<=p[m+1].x) p[++n]=p2[i];
}
sort(p+1, p+1+n);
int k1=1, k2=L; ans=linf;
rep(i, 1, n)
{
double x=p[i].x;
while (k1<m && g[k1].b.x<x) k1++;
while (k2<R && p2[k2].x<x) k2++;
line v; v.a.x=v.b.x=x, v.a.y=1, v.b.y=2;
ans=min(ans, inter(v, q[k2]).y-inter(v, g[k1]).y);
}
printf("%.3lf\n", ans);
return 0;
}

最新文章

  1. jQuery的61种选择器
  2. links and softwares
  3. onSaveInstanceState() 和 onRestoreInstanceState()
  4. hadoop小试
  5. innodb的表最大限制
  6. Xcode环境下OpenGL C++ GLFW开发环境搭建
  7. (转载)IO-同步、异步、阻塞、非阻塞
  8. 第20章 DLL高级技术(3)
  9. poj 3328(多起点多终点的最短路)
  10. Ubuntu中使用pyUSB读取鼠标或键盘的数据程序
  11. vs2012新建实体数据模型(EF)时无Mysql数据源
  12. ECLIPSE IDEA 调音 1
  13. iptables防火墙详解
  14. 10分钟精通SharePoint - SharePoint升级
  15. 使用mitmproxy嗅探双向认证ssl链接——嗅探AWS IoT SDK的mqtts
  16. [原创]X-HDL 4.2安装与使用
  17. Vector集合
  18. Python3基础 ** 幂运算 // 整除运算
  19. 中文路径读取乱码,json乱码
  20. polymer入门例子-已过时

热门文章

  1. CDQ分治入门
  2. JavaScript 交换两个变量的值
  3. C/C++程序基础 (六)面向对象
  4. node 中的redis使用
  5. 十、MySQL 删除数据表
  6. 配置vim nginx.conf高亮
  7. linux 命令学习(持续完善中...)
  8. 16.VUE学习之-v-show的使用与v-if的差异对比
  9. I miss you, Jenny【我想念你,jenny】
  10. collections模块简介