1502: [NOI2005]月下檸檬樹
Time Limit: 5 Sec??Memory Limit: 64 MBSubmit: 1017??Solved: 562
[Submit][Status][Discuss]
Description
Input
文件的第1行包含一個整數n和一個實數alpha，表示檸檬樹的層數和月亮的光線與地面夾角(單位為弧度)。第2行包含n+1個實數h0,h1,h2,…,hn，表示樹離地的高度和每層的高度。第3行包含n個實數r1,r2,…,rn，表示檸檬樹每層下底面的圓的半徑。上述輸入文件中的數據，同一行相鄰的兩個數之間用一個空格分隔。輸入的所有實數的小數點后可能包含1至10位有效數字。
Output
輸出1個實數，表示樹影的面積。四舍五入保留兩位小數。
Sample Input
10.0 10.00 10.00
4.00 5.00
Sample Output
HINT
1≤n≤500，0.3
Source
Solution
一道計算集合比較蛋疼的題目
檸檬樹吉他譜掃弦版？當時的正解應該是分類討論+特判很多東西再直接求面積，但是發現這題非常適合辛普森積分所以就直接上了
那么先是辛普森積分的公式：
對于某些不易計算曲線的一種近似方法，能自動調整精度，但誤差較大（比較平滑的曲線非常適合）
具體的計算流程就是，計算[l,mid]以及[mid,r]與直接計算[l,r]的結果相比較，如果近似則返回[l,r]即可，否則可以分別遞歸細化
這種做法非常好卡，一種最簡單的卡法：
這樣一開始就會直接返回，然而遞歸下去才能求的更精確的值
---------------------------------------------------分割線---------------------------------------------------
檸檬樹吉他譜原版、首先我們考慮這題的投影，圓投下來，和之前完全一樣，所以投影本質是一些圓和他們的公切線組成的圖形求面積
發現其實是軸對稱圖形，所以可以考慮直接利用掃描線+自適應Simpson來做
掃描線被覆蓋部分的長度的函數F(x)在這個圖形的區間中是連續的，因此不必考慮將整個圖形拆成若干個一坨一坨的圖形再求積分，少了不少細節。
無論掃描線在何處，它被覆蓋的部分也是永遠是連續的，因此可以暴力找每個圓是否和掃描線有交，每條公切線段是否和掃描線有交，然后取掃描線被覆蓋長度的最大值即可
那么至于求公切線，比較簡單，給出詳細方法：
首先我們得到：$l=C_{i+1}.O.x-C_{i+1}.O.x$
那么我們可以算出：$sin\alpha = (R-r)/l$，$cos\alpha = \sqrt{1-sin^2\alpha}$（考慮從$C_{i+1}.O$向$R$做垂線）
那么可以算出切點：
$C_{i}.A=(C_{i}.O.x+R*sin\alpha,R*cos\alpha)$
$C_{i+1}.A=(C_{i+1}.O.x+r*sin\alpha,r*cos\alpha)$
這題的細節比較麻煩，注意特判圓被另一個圓直接覆蓋的情況
檸檬樹 簡譜、---------------------------------------------------分割線---------------------------------------------------
這道題還需要注意一下精度問題
個人測試：eps=1e-5是可行最優
eps=1e-12 ? --> 5s
eps=1e-8 ? ? --> 1s
檸檬樹王若琳中文版吉他譜、eps=1e-5 ? ? --> 0.5s
eps=1e-3/-4 --> Wrong_Answer
Code
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define MAXN 1010 double alpha; int N,num; #define INF 1e12 #define eps 1e-5 struct Point { double x,y; Point (double X=0,double Y=0) {x=X; y=Y;} }; struct Circle { double r; Point c; Circle(Point C=(Point){0,0},double R=0) {c=C; r=R;} }C[MAXN]; struct Line { Point s,t; double k,b; Line(Point S=(Point){0,0},Point T=(Point){0,0}) { s=S,t=T; if (s.x>t.x) swap(s,t); k=(s.y-t.y)/(s.x-t.x); b=s.y-k*s.x; } double f(double x) {return k*x+b;} }l[MAXN]; int dcmp(double x) {if (fabs(x)<eps) return 0; return x<0? -1:1;} double F(double x) { double re=0; for (int i=1; i<=N; i++) //枚舉圓是否與掃描線有交 { double d=fabs(x-C[i].c.x); if (dcmp(d-C[i].r)>0) continue; double len=2*sqrt(C[i].r*C[i].r-d*d); re=max(re,len); } for (int i=1; i<=num; i++) //枚舉公切線if (x>=l[i].s.x && x<=l[i].t.x) re=max(re,2*l[i].f(x)); return re; } //利用掃描線去判斷 double Calc(double l,double r) {double mid=(l+r)/2; return (F(l)+F(r)+F(mid)*4)*(r-l)/6;} double Simpson(double l,double r,double now) { double mid=(l+r)/2; double x=Calc(l,mid),y=Calc(mid,r); if (!dcmp(now-x-y)) return now; else return Simpson(l,mid,x)+Simpson(mid,r,y); } void Solve() { double L=INF,R=-INF; for (int i=1; i<=N+1; i++) L=min(L,C[i].c.x-C[i].r),R=max(R,C[i].c.x+C[i].r); // printf("%lf\n%lf\n",L,R); for (int i=1; i<=N; i++) { double d=C[i+1].c.x-C[i].c.x; if (dcmp(d-fabs(C[i].r-C[i+1].r))<0) continue; //特判小圓被大圓覆蓋的情況double sina=(C[i].r-C[i+1].r)/d,cosa=sqrt(1-sina*sina); l[++num]=(Line){(Point){C[i].c.x+C[i].r*sina,C[i].r*cosa},(Point){C[i+1].c.x+C[i+1].r*sina,C[i+1].r*cosa}}; } printf("%.2lf\n",Simpson(L,R,Calc(L,R))); } int main() { scanf("%d%lf",&N,&alpha); double h,r; for (int i=1; i<=N+1; i++) scanf("%lf",&h), C[i]=(Circle){((Point){(h/tan(alpha))+C[i-1].c.x,0}),0}; for (int i=1; i<=N; i++) scanf("%lf",&r),C[i].r=r; // for (int i=1; i<=N+1; i++) // printf("%d %.2lf %.2lf\n",i,C[i].c.x,C[i].r); Solve(); return 0; }
晚上頹這道‘模版題’簡直不要太爽，來個人求一下我的心里陰影面積吧QAQ
