P1663 山

admin

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.

黄煦喆

感觉还可以用半平面做

黄煦喆

计算几何 叉积法

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. }
    

复制代码