华师一附中OI组

标题: P1663 山 [打印本页]
作者: admin    时间: 2018-7-24 18:32
标题: P1663 山
https://www.luogu.org/problemnew/show/P1663

题目描述
给出一座山，如图。



现在要在山上的某个部位装一盏灯，使得这座山的任何一个部位都能够被看到。

给出最小的y坐标，如图的+号处就是y坐标最小的安装灯的地方。

输入输出格式
输入格式：
第一行一个数N，表示这座山由N个点构成；

接下来N行从左到右给出了这座山的构造情况，每行两个数Xi、Yi，表示一个折点，保证Xi>Xi-1

输出格式：
仅输出一行，为最小的y坐标，当你的答案与标准答案相差不超过0.01时，则被认为是正确的。

输入输出样例
输入样例#1：
6
0 0
10 0
11 1
15 1
16 0
25 0
输出样例#1：
3.00
说明
数据规模：

30%的数据，1≤N≤50；

100%的数据，1≤N≤5000；0≤Xi，Yi≤100000，保证答案不超过1000000.

作者: 黄煦喆    时间: 2018-8-24 19:47
计算几何 叉积法
  1. #include<iostream>
  2. #include<iomanip>
  3. #include<cstdio>
  4. using namespace std;
  5. int n,bb;
  6. double const eps=1e-3;
  7. double a,b,ans,midx,midy;
  8. double ly=1,ry=1000000,r[5001],c[5001];
  9. struct cPoint
  10. {
  11.     double x,y;
  12.     cPoint(double xx,double yy):x(xx),y(yy) {}
  13. };
  14. struct cVector
  15. {
  16.     double x,y;
  17.     cVector(double xx,double yy): x(xx),y(yy) {}
  18. };
  19. cVector operator- (cPoint A,cPoint B)
  20. {
  21.     return cVector(B.x-A.x,B.y-A.y);
  22. }
  23. double operator^ (cVector s,cVector t)
  24. {
  25.     return s.x*t.y-t.x*s.y;
  26. }
  27. int main()
  28. {
  29.     cin>>n;
  30.     for(int i=1; i<=n; i++)cin>>r[i]>>c[i];
  31.     while(ry-ly>eps)
  32.     {
  33.         midy=(ly+ry)/2.0;
  34.         bb=1;
  35.         double lx=1,rx=r[n];
  36.         while(rx-lx>eps&&bb)
  37.         {
  38.             bb=0;
  39.             midx=(lx+rx)/2.0;
  40.             for(int i=1;i<n&&!bb;i++)
  41.                 if(((cPoint(r[i],c[i])-cPoint(midx,midy))^(cPoint(r[i+1],c[i+1])-cPoint(midx,midy)))<-eps)
  42.                 {
  43.                     if(midx>r[i+1])bb=1;
  44.                     else if(midx<r[i])bb=2;
  45.                 }
  46.             if(bb==1)rx=midx-eps;
  47.             else if(bb==2)lx=midx+eps;
  48.         }
  49.         if(!bb)
  50.         {
  51.             ans=midy;
  52.             ry=midy-eps;
  53.         }
  54.         else ly=midy+eps;
  55.     }
  56.     printf("%.2f",ans);
  57.     return 0;
  58. }
复制代码
作者: 黄煦喆    时间: 2018-8-29 16:23
感觉还可以用半平面做



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2