半平面交。

半平面指的就是一条直线的左面(也不知道对不对)

半平面交就是指很多半平面的公共部分。

这道题的解一定在各条直线的半平面交中。

而且瞭望塔只可能在各个点或者半平面交折线的拐点处。

求出半平面交,枚举即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define eps 1e-7
using namespace std;
const int maxn = 300 + 10; struct Point {
double x,y;
}p[maxn],t; struct Line {
double k,b; void init(Point p1,Point p2) {
k=(p1.y-p2.y)/(p1.x-p2.x);
b=p2.y-k*p2.x;
}
}l[maxn],s[maxn]; int n,sp;
double res=1e11; bool cmp(Line x,Line y) {
if(abs(x.k-y.k)<eps) return x.b<y.b;
return x.k<y.k;
} Point inter(Line l1,Line l2) {
Point res;
res.x=(l2.b-l1.b)/(l1.k-l2.k);
res.y=l1.k*res.x+l1.b;
return res;
} void push(Line l) {
while(sp>=2 && inter(s[sp],l).x < inter(s[sp-1],s[sp]).x) sp--;
s[++sp]=l;
} double f(double x) {
double res=0;
for(int i=1;i<=sp;i++) res=max(res,s[i].k*x+s[i].b);
return res;
} double g(double x) {
int i;
for(i=n;i&&x<p[i].x;i--);
return p[i].y+(x-p[i].x)/(p[i+1].x-p[i].x)*(p[i+1].y-p[i].y);
} int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf",&p[i].x);
for(int i=1;i<=n;i++) scanf("%lf",&p[i].y);
for(int i=1;i<n;i++) l[i].init(p[i],p[i+1]);
sort(l+1,l+n,cmp);
for(int i=1;i<n;i++) if(i==n-1 || abs(l[i].k-l[i+1].k)>eps) push(l[i]); for(int i=1;i<=n;i++) res=min(res,f(p[i].x)-p[i].y);
for(int i=1;i<sp;i++) {
t=inter(s[i],s[i+1]);
res=min(res,t.y-g(t.x));
}
printf("%.3lf\n",res);
return 0;
}

最新文章

  1. PHP 7 的新特性
  2. sqoop中,如果数据中本身有换行符,会导致数据错位
  3. Python - 利用pip管理包
  4. BZOJ3830 : [Poi2014]Freight
  5. jquery CDN(内容分发网络)使用
  6. Shared and Exclusive Locks 共享和排它锁
  7. 【转】C++中的位拷贝与值拷贝
  8. Linux 二进制包安装MySQL的一些问题
  9. 使用命令部署wsp包,并将其部署到不同的web应用程序
  10. Nginx 防CC攻击拒绝代理访问
  11. java LinkedLis t的26种使用方法
  12. ORA-04028: cannot generate diana for object xxx
  13. [BZOJ1112] [POI2008] 砖块Klo (treap)
  14. Linux磁盘管理及LVM讲解(week2_day2)--技术流ken
  15. 【Spark-SQL学习之三】 UDF、UDAF、开窗函数
  16. Ubuntu 16.04下配置intel opencl环境
  17. python中读取文件的read、readline、readlines方法区别
  18. 学习笔记之Microsoft Office 365
  19. readv writev示例程序
  20. P1102 A-B数对

热门文章

  1. js中的null VS undefined
  2. javascript设计模式--中介者模式(Mediator)
  3. Delphi的Socket编程步骤
  4. HDU 1548 A strange lift (Dijkstra)
  5. hadoop,spark,linux上常用命令
  6. Codeforces Round #336 (Div. 2) D. Zuma 区间dp
  7. java如何追加写入txt文件
  8. daatable动态创建
  9. div滚动条
  10. My SQL InnoDB 1217 - Cannot delete or update a parent row:aforeign key constraint fals