You just bought an “artistic” aquarium tank that has an interesting shape, and you poured L litres of water into the tank. How high is the water in the tank?
When you look at this tank from one side, it has the shape of a convex polygon. This polygon has exactly two vertices on the table (y-coordinates are 0), and all other vertices have positive y-coordinates. There are also exactly two vertices with maximum y-coordinates, and water is poured into the opening between these two vertices. This aquarium tank has a depth of D centimetres. The tank is glued to the table, so no matter what shape it has, it keeps its position and does not tip over. All coordinates and lengths in this problem are given in centimetres. It should be noted that each cubic metre is equivalent to 1 000 litres.
An illustration showing the configuration of the tank of the first sample input is given below:
The input consists of a single test case. The first line contains an integer N (4 ≤ N ≤ 100) giving the number of vertices in the polygon. he next line contains two integers D and L, where 1 ≤ D ≤ 1000 is he depth of the aquarium tank and 0 L 2 000 is the number of litres f water to pour into the tank. The next N lines each contains two integers, giving the (x, y) coordinates of the vertices of the convex polygon in counterclockwise order. The absolute values of x and y are at most 1 000. You may assume that the tank has a positive capacity, and you never pour more water than the tank can hold.
Print the height of the water (in centimetres) in the aquarium tank on a line to 2 decimal places.
4 30 50 20 0 100 0 100 40 20 40
20.83
尋找&星空の孩子
1 #include<cstdio>
2 #include<cmath>
3 #include<iostream>
4 #define PI acos(-1.0)
5 using namespace std;
6
7 struct Point
8 {
9 double x,y;
10 Point(double x=0,double y=0):x(x),y(y) {}
11
12 };
13
14 double hmax;
15 double D,L;
16
17 typedef Point Vector;//Vector只是Point的別名
18
19 //向量+向量=向量; 向量+點=點
20 Vector operator + (Vector A,Vector B)
21 {
22 return Vector(A.x+B.x,A.y+B.y);
23 }
24
25 //點-點=向量
26 Vector operator - (Point A,Point B)
27 {
28 return Vector(A.x-B.x,A.y-B.y);
29 }
30
31 //向量*數=向量
32 Vector operator * (Vector A,double p)
33 {
34 return Vector(A.x*p,A.y*p);
35 }
36
37 //向量/數=向量
38 Vector operator / (Vector A,double p)
39 {
40 return Vector(A.x/p,A.y/p);
41 }
42
43
44 //
45 bool operator < (const Point& a,const Point& b)
46 {
47 return a.x<b.x||(a.x==b.x && a.y<b.y);
48 }
49
50 //
51 const double eps = 1e-8;
52 //三態函數
53 int dcmp(double x)
54 {
55 if(fabs(x)<eps)return 0;
56 else return x < 0 ? -1 : 1;
57 }
58 //相等
59 bool operator == (const Point& a,const Point& b)
60 {
61 return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
62 }
63
67 double Dot(Vector A,Vector B)
68 {
69 return A.x*B.x+A.y*B.y;
70 }
71 double length(Vector A)
72 {
73 return sqrt(Dot(A,A));
74 }
75 double Angle(Vector A,Vector B)
76 {
77 return acos(Dot(A,B)/length(A)/length(B));
78 }
79
84 double Cross(Vector A,Vector B)
85 {
86 return A.x*B.y-B.x*A.y;
87 }
88 double Area2(Point A,Point B,Point C)
89 {
90 return Cross(B-A,C-A);
91 }
92
93 double PArea(Point *p,int n)
94 {
95 double area=0;
96 for(int i=0; i<n; i++)
97 {
98 area+=Cross(p[i],p[(i+1)%n]);
99 // printf("area=%f\n",area);
100 }
101 return fabs(area/2);
102 }
103
104 /*******兩直線交點*******/
105 //調用前確保兩條直線P+tv和Q+tv有唯一交點，當且僅當Cross(v,w)非0;
106 Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)
107 {
108 Vector u=P-Q;
109 // printf("P=(%f,%f),v=(%f,%f),Q=(%f,%f),w=(%f,%f)\n",P.x,P.y,v.x,v.y,Q.x,Q.y,w.x,w.y);
110 // if(Cross(v,w))
111 // {
112 // double t=Cross(w,u)/Cross(v,w);//精度高的時候，考慮自定義分數類
113 // return P+v*t;
114 // }
115 // else
116 // return ;
117 //printf("t= %lf\t%lf",Cross(w,u),Cross(v,w));
118 return P+v*Cross(w,u)/Cross(v,w);
119 }
120 //輸入函數
121 Point read_point(Point &P)
122 {
123 scanf("%lf%lf",&P.x,&P.y);
124 hmax=max(hmax,P.y);
125 return P;
126 }
127 Point get_point(Point a, Point b, double y0)
128 {
129 if(fabs(a.x - b.x) < eps) return Point(a.x, y0);
130 double bi = (y0 - a.y) / (b.y - a.y);
131 return Point(a.x + bi * (b.x - a.x), a.y + bi * (b.y - a.y));
132 }
133 int main()
134 {
135 Point po[105],Q[105];
136 int T,n,q,i;
137
138 // freopen("debug//secret-tank-03.in","r",stdin);
139 while(scanf("%d",&n)!=EOF)
140 {
141 scanf("%lf%lf",&D,&L);
142 hmax=0;
143 for(i=0; i<n; i++)
144 {
145 read_point(po[i]);
146 // printf("----[%lf]\n",po[i]);
147 }
148 // po[n]=po[0];
149 // po[n+1]=po[1];
150 // Q[0]=po[0];
151 // Q[1]=po[1];
152 // printf("Q[%d]=%lf\n\n",1,po[1]);
153 double d=0,h=hmax;
154 while(h-d>eps)
155 {
156 q=0;
157 int per=n-1;
158 double m=(d+h)/2;
159 // printf("m=%lf\n",m);
160 // getchar();
161 Point M(0,m);
162 Vector w(1,0);
163 for(int i=0; i<n; i++)
164 {
165 // if(i==0&&(m-po[i].y)>eps){Q[q++]=po[i];continue;}
166
167
168 // else if((m-po[i].y)==eps)
169 // {
170 // Q[q++]=po[i];
171 // }
172 if((m-po[i].y)*(m-po[per].y)<eps)
173 {
174 // printf("------------------------------------------------------\n");
175 // Vector PP=po[i]-po[per];
176 // Q[q++]=GetLineIntersection(po[per],PP,M,w);
177 Q[q++]=get_point(po[i],po[per],m);
178 }
179 if((m-po[i].y)>eps)
180 {
181 // if(i==1) Q[q++]=po[i-1];
182 Q[q++]=po[i];
183 }
184 per=i;
185 // printf("Q[%d]=(%f,%f)\n",q-1,Q[q-1].x,Q[q-1].y);
186 }
187 // Q[q]=Q[0];
188 // if(m==20)
189 // for(int i=0;i<q;i++)
190 // {
191 // printf("Q[%d]=(%f,%f)\n",i,Q[i].x,Q[i].y);
192 // }
193 double area=PArea(Q,q);
194 // printf("L=%f\tV=%lf\tm=%lf\n",L*1000,area*D,m);
195 if(L*1000-area*D>eps) d=m;
196 else h=m;
197
198 }
199 printf("%.2f\n",d);
200 }
201 return 0;
202 }
203
204 /**************************************************************
205 Problem: 1634
206 User: aking2015
207 Language: C++
208 Result: Accepted
209 Time:0 ms
210 Memory:1496 kb
211 ****************************************************************/
1 #include<cstdio>
2 #include<cmath>
3 #include<iostream>
4 #define PI acos(-1.0)
5 using namespace std;
6
7 struct Point
8 {
9 double x,y;
10 Point(double x=0,double y=0):x(x),y(y) {}
11
12 };
13
14 double hmax;
15 double D,L;
16
17 typedef Point Vector;
18
19 Vector operator + (Vector A,Vector B)
20 {
21 return Vector(A.x+B.x,A.y+B.y);
22 }
23
24 Vector operator - (Point A,Point B)
25 {
26 return Vector(A.x-B.x,A.y-B.y);
27 }
28
29 Vector operator * (Vector A,double p)
30 {
31 return Vector(A.x*p,A.y*p);
32 }
33
34 Vector operator / (Vector A,double p)
35 {
36 return Vector(A.x/p,A.y/p);
37 }
38
39 bool operator < (const Point& a,const Point& b)
40 {
41 return a.x<b.x||(a.x==b.x && a.y<b.y);
42 }
43
44 const double eps = 1e-8;
45
46 int dcmp(double x)
47 {
48 if(fabs(x)<eps)return 0;
49 else return x < 0 ? -1 : 1;
50 }
51 bool operator == (const Point& a,const Point& b)
52 {
53 return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
54 }
55
56 double Dot(Vector A,Vector B)
57 {
58 return A.x*B.x+A.y*B.y;
59 }
60 double length(Vector A)
61 {
62 return sqrt(Dot(A,A));
63 }
64 double Angle(Vector A,Vector B)
65 {
66 return acos(Dot(A,B)/length(A)/length(B));
67 }
68
69 double Cross(Vector A,Vector B)
70 {
71 return A.x*B.y-B.x*A.y;
72 }
73 double Area2(Point A,Point B,Point C)
74 {
75 return Cross(B-A,C-A);
76 }
77
78 double PArea(Point *p,int n)
79 {
80 double area=0;
81 for(int i=0; i<n; i++)
82 {
83 area+=Cross(p[i],p[(i+1)%n]);
84 }
85 return fabs(area/2);
86 }
87
88 Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)
89 {
90 Vector u=P-Q;
91 return P+v*Cross(w,u)/Cross(v,w);
92 }
93 Point read_point(Point &P)
94 {
95 scanf("%lf%lf",&P.x,&P.y);
96 hmax=max(hmax,P.y);
97 return P;
98 }
99 Point get_point(Point a, Point b, double y0)
100 {
101 if(fabs(a.x - b.x) < eps) return Point(a.x, y0);
102 double bi = (y0 - a.y) / (b.y - a.y);
103 return Point(a.x + bi * (b.x - a.x), a.y + bi * (b.y - a.y));
104 }
105 int main()
106 {
107 Point po[105],Q[105];
108 int T,n,q,i;
109 while(scanf("%d",&n)!=EOF)
110 {
111 scanf("%lf%lf",&D,&L);
112 hmax=0;
113 for(i=0; i<n; i++)
114 {
115 read_point(po[i]);
116 }
117 double d=0,h=hmax;
118 while(h-d>eps)
119 {
120 q=0;
121 int per=n-1;
122 double m=(d+h)/2;
123 Point M(0,m);
124 Vector w(1,0);
125 for(int i=0; i<n; i++)
126 {
127 if((m-po[i].y)*(m-po[per].y)<eps)
128 {
129 Vector PP=po[i]-po[per];
130 Q[q++]=GetLineIntersection(po[per],PP,M,w);
131 // Q[q++]=get_point(po[i],po[per],m);
132 }
133 if((m-po[i].y)>eps)
134 {
135 Q[q++]=po[i];
136 }
137 per=i;
138 }
139 double area=PArea(Q,q);
140 if(L*1000-area*D>eps) d=m;
141 else h=m;
142 }
143 printf("%.2f\n",d);
144 }
145 return 0;
146 }
147
148 /**************************************************************
149 Problem: 1634
150 User: aking2015
151 Language: C++
152 Result: Accepted
153 Time:0 ms
154 Memory:1500 kb
155 ****************************************************************/
