NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2010高中組決賽
 NPSC 2010 高中組 決賽 G.

作者 主題: NPSC 2010 高中組 決賽 G.  (閱讀 3022 次)

liouzhou_101

  • 初級會員
  • **
  • 文章數: 44
    • 檢視個人資料
NPSC 2010 高中組 決賽 G.
« 於: 八月 13, 2011, 09:33:42 pm »

題目簡述:
給你N(0<=N<=10)個相離的圓,叫你求出從點(0,0)到點(1000,1000)的最短路徑長度,使得路徑不經過任何圓的內部。

題目分析:
這題是一道最短路徑的題目,應該建立最短路模型,然後用SPFA或dijkstra求單源最短路。
首先有如下定理。

定理:最短路徑必定是由多條線段或已知圓的圓弧首尾相接而成的,這些線段和已知圓的圓弧的兩端點必定是兩圓的公切線上的切點或是一個圓與過起點或終點的切線上的切點。
證明:略。

這樣,問題的核心便轉移到了如何求所有兩圓的公切線上的切點和所有圓與過起點或終點的切線上的切點。

一個圓與過起點或終點的切線上的切點,可以看作是該圓與圓心為起點或終點,半徑為0的圓的公切線上的切點。

設圓的表示法為圓(x,y,r),表示該圓圓心為(x,y),半徑為r。
設距離函數dis((x1,y1),(x2,y2))表示兩點(x1,y1)和(x2,y2)之間的距離,故有
dis((x1,y1),(x2,y2))= √((x1-x2)2+(y1-y2)2)。
« 上次編輯: 八月 13, 2011, 09:37:37 pm 由 liouzhou_101 »
記錄

liouzhou_101

  • 初級會員
  • **
  • 文章數: 44
    • 檢視個人資料
回覆: NPSC 2010 高中組 決賽 G.
« 回覆 #1 於: 八月 13, 2011, 09:38:29 pm »

以下求的是兩圓的公切線上的切點。

由於兩圓相離,故兩圓的公切線有4條。
由此,設兩個圓分別為(x1,y1,r1)和(x2,y2,r2),圓心分別為O1,O2。
由於對稱性,不妨設r1<=r2。
設圓心距為d= dis((x1,y1),(x2,y2))。
設向量a=(x1-x2,y1-y2)。

①兩個圓都在公切線的同側,這樣的公切線有2條。
若兩圓半徑相等,
設向量w•a = 0,且|w| = r1,
則4個切點分別為O1±w和O2±w。
若兩圓半徑不相等,
設這兩條公切線的交點為P,
則由三角形相似得PO1/PO2 = r1/r2。
設PO1= l (注:這裏l是L的小寫),則有
l / (l+d) = r1/r2
解得
l = dr1/( r1+r2)
故P= O1+l/d•a。
這樣,
在圓O1上的切點,可以看做圓O1與圓(xP,yP, √(l2-r12))的交點;
在圓O2上的切點,可以看做圓O2與圓(xP,yP, √((l+d)2-r22))的交點。
②兩個圓在公切線異側,這樣的公切線有2條。
設這兩條公切線的交點為P,
則由三角形相似得PO1/PO2 = r1/r2。
設PO1= d1,PO2= d2。
則有
d1/d2 = r1/r2
d1+d2=d
解得
d1=dr1/( r1+r2)
d2=dr2/( r1+r2)
又設P(xP,yP)
則有
(x1 - xP) / (x2 - xP) = r1/r2
(y1 - yP) / (y2 - yP) = r1/r2
解得
xP = (x1 r2 + x2 r1) / (r1+r2)
yP = (y1 r2 + y2 r1) / (r1+r2)
這樣,
在圓O1上的切點,可以看做圓O1與圓(xP,yP,d1)的交點;
在圓O2上的切點,可以看做圓O2與圓(xP,yP,d2)的交點。

至此,求兩圓公切線上的切點已經轉化為求兩相交圓的交點。
記錄

liouzhou_101

  • 初級會員
  • **
  • 文章數: 44
    • 檢視個人資料
回覆: NPSC 2010 高中組 決賽 G.
« 回覆 #2 於: 八月 13, 2011, 09:39:29 pm »

以下求兩圓的交點。

設兩個圓分別為(x1,y1,r1)和(x2,y2,r2),圓心分別為O1,O2。
設圓心距為d= dis((x1,y1),(x2,y2))。
設向量a=(x1-x2,y1-y2)。
由於兩圓相交則有d< r1 + r2。
設交點分別為P1和P2,P1P2與O1O2的交點為P(xP,yP),PP1=PP2=h。
設三角形O1O2P1的面積為S,有海倫公式得
S=√p(p- r1)(p- r2)(p-d)
其中p=(r1+r2+d)/2。
由三角形面積一定得h=2S / d。
設PO1= d1,PO2= d2。
故有
d12= r12 + h2
d22= r22 + h2

PO1/PO2= d1/d2

(x1 - xP) / (x2 - xP) = d1/d2
(y1 - yP) / (y2 - yP) = d1/d2
解得
xP = (x1 d2 + x2 d1) / (d1+d2)
yP = (y1 d2 + y2 d1) / (d1+d2)
設向量w•a = 0,且|w| = h,
故P1,2 = P±w。

至此,已經解決了求兩圓交點的問題,從而解決了求兩圓公切線上的切點的問題。
記錄

liouzhou_101

  • 初級會員
  • **
  • 文章數: 44
    • 檢視個人資料
回覆: NPSC 2010 高中組 決賽 G.
« 回覆 #3 於: 八月 13, 2011, 09:40:33 pm »

接下來,我們應該要判斷兩個點之間是否可以直接相連(即通過一條直線或一條已知圓的圓弧相連)。

設兩點為(x1,y1)和(x2,y2),不妨設x1<= x2。

顯然,當兩點在同一圓上時,我們只需求得兩端點為這兩點的劣弧長度即可。
設該圓為(x,y,r),所求劣弧長為l。
設向量a = (x1-x,y1-y),向量b = (x2-x,y2-y)。
則l=<a, b>•r。
而cos<a, b>=a•b / (|a|•|b|),故可求出<a, b>。
這裏有
arccos x =
arctan((√(1-x2)) / x)       (x>0)
π/2                   (x=0)
π- arccos (–x)           (x<0)

當兩點不在同一圓上時,我們只需判斷這兩點組成的線段與所有圓的距離是否大於該圓半徑,若對於所有圓,這兩點組成的線段與圓的距離都大於該圓半徑,則這兩點之間可以通過一條直線相連,長度是d= dis((x1,y1),(x2,y2))。

於是該問題便轉移到了求一條線段與已知圓的距離。
記錄

liouzhou_101

  • 初級會員
  • **
  • 文章數: 44
    • 檢視個人資料
回覆: NPSC 2010 高中組 決賽 G.
« 回覆 #4 於: 八月 13, 2011, 09:41:19 pm »

以下求一條線段與已知圓的距離。

設線段的兩端點為(x1,y1)和(x2,y2),解析式為Ax+By+C=0,已知圓為(x0,y0,r0),圓心到直線Ax+By+C=0的距離為d。
故過圓心與直線Ax+By+C=0垂直的直線方程為Bx-Ay+Ay0-Bx0=0。
設圓心在直線Ax+By+C=0上的投影為P(xP,yP)。
有方程組
AxP +ByP+C=0
BxP -AyP+Ay0-Bx0=0
可以解得P(xP,yP)。
於是

d=
dis((x0,y0),(xP,yP))                                       (当x1<=xP<=x2时)
Min{ dis((x0,y0),(x1,y2)),dis((x0,y0),(x2,y2)) }                (否则)

至此,解決了求已知線段與已知圓的距離,其實就是已知直線與已知點的距離。
該問題具有一般性。
« 上次編輯: 八月 14, 2011, 11:06:26 am 由 liouzhou_101 »
記錄

liouzhou_101

  • 初級會員
  • **
  • 文章數: 44
    • 檢視個人資料
回覆: NPSC 2010 高中組 決賽 G.
« 回覆 #5 於: 八月 13, 2011, 09:41:56 pm »

這樣就可以構造出了最短路模型,即對於一個無向圖G=(E,V),求節點s到節點t的最短路徑,這可以用SPFA或dijkstra來求的。

最後,我們來分析一下空間和時間的開銷,由於有O(N)個圓,他們互相的公切線上的切點個數是O(N2)的,而點與點之間邊的個數是O(N4)的。
於是空間複雜度約為O(N4),時間複雜度約為求最短路徑長度的時間複雜度。

另外,由於此題做的都是浮點數運算,存在不小的誤差,具體實現時要處處小心。

至此,此題得到完美解決。
« 上次編輯: 八月 13, 2011, 09:47:21 pm 由 liouzhou_101 »
記錄

david942j

  • 新手
  • *
  • 文章數: 18
    • 檢視個人資料
Re: NPSC 2010 高中組 決賽 G.
« 回覆 #6 於: 二月 06, 2012, 04:39:58 pm »

辛苦liouzhou_101打了這麼多XDD
而且還用繁體字OAO"
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
Re: NPSC 2010 高中組 決賽 G.
« 回覆 #7 於: 二月 06, 2012, 04:43:05 pm »

是的, 辛苦 liouzhou_101 了,
只可惜這個系統沒有按 "讚" 的功能 XD
記錄

david942j

  • 新手
  • *
  • 文章數: 18
    • 檢視個人資料
Re: NPSC 2010 高中組 決賽 G.
« 回覆 #8 於: 八月 06, 2012, 09:56:39 pm »

與原PO作法相同
公切線與距離等可善用cross及dot運算讓code簡潔不少
代碼: [選擇]
//by david942j
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
const int N=12;
const double EPS=1e-5;
struct node{
int p;
double c;
node *next;
}h[N*N*N];
struct unit{
double x,y;
int idx;
unit(double X,double Y){x=X;y=Y;}
unit(){}
unit operator-(const unit &A)const
{
unit tmp(x-A.x,y-A.y);
return tmp;
}
unit operator+(const unit &A)const
{
unit tmp(x+A.x,y+A.y);
return tmp;
}
unit operator*(const double &A)const
{
unit tmp(x*A,y*A);
return tmp;
}
double operator*(const unit &A)const
{return x*A.y-y*A.x;}
double dot(const unit &A)const
{return x*A.x+y*A.y;}
inline double len(){return sqrt(x*x+y*y);}
inline void normalize(){double l=len();x/=l;y/=l;}
bool operator<(const unit &B)const
{
unit A(x,y);
if(fabs(A.y)<EPS&&fabs(B.y)<EPS)return A.x>B.x;
if(A.y>0&&B.y<0)return true;
if(B.y>0&&A.y<0)return false;
return A*B>0;
}
//inline void out(){printf("- %.2lf %.2lf\n",x,y);}
}C[N];
int nodetop;
void add(int x,int y,double c)
{
//printf("add %d %d %lf\n",x,y,c);
node *tmp=new node;
tmp->p=y;tmp->c=c;
tmp->next=h[x].next;
h[x].next=tmp;
}
std::vector<unit>V[N];
void PonC(std::vector<unit>&V,unit &C,double &r)
{
int n=V.size();
for(int i=0;i<n;i++){
int idx=V[i].idx;
V[i]=V[i]-C;
V[i].idx=idx;
}
std::sort(V.begin(),V.end());
V.push_back(V[0]);
for(int i=0;i<n;i++)
{
double len=r*acos(V[i].dot(V[i+1])/r/r);
add(V[i].idx,V[i+1].idx,len);
add(V[i+1].idx,V[i].idx,len);
}
}
double R[N];
int n;
void PtoC(unit A,unit C,double r,unit &p,unit &q)
{
unit u=C-A;
double l=u.len(),d=sqrt(l*l-r*r);
u.normalize();
unit v(u.y,-u.x);
u=u*(d*d/l)+A;
v=v*(d*r/l);
p=u+v;
q=u-v;
}
void newnode(unit A,int pos)
{
//printf("%d: %lf %lf on %d\n",nodetop,A.x,A.y,pos);
h[A.idx=nodetop++].next=NULL;
V[pos].push_back(A);
}
inline void swap(int &A,int &B){int tmp=A;A=B;B=tmp;}
bool ok(unit A,unit B)
{
unit u=B-A,v;
double L=u.len();
u.normalize();
for(int i=1;i<=n;i++)
{
v=C[i]-A;
double t=u.dot(v)/L;
if(t<EPS||t>1.0-EPS)continue;
if(R[i]>fabs(u*v)/u.len()+EPS)return false;
}
return true;
}
void calc(int p1,int p2)
{
if(R[p1]>R[p2])swap(p1,p2);
double &r1=R[p1],&r2=R[p2];
unit &c1=C[p1],&c2=C[p2],A[2]={(c2-c1)*(r1/(r1+r2))+c1,(c1-c2)*(r2/(r2-r1))+c2};
unit a1,b1,a2,b2;
for(int i=0;i<2;i++)
{
if(i&&fabs(r1-r2)<EPS)
{
unit u=c2-c1;
u.normalize();
unit v(u.y,-u.x);
a1=v*r1+c1;
a2=v*r2+c2;
b1=v*-r1+c1;
b2=v*-r2+c2;
}
else{
PtoC(A[i],c1,r1,a1,b1);
PtoC(A[i],c2,r2,a2,b2);
}
if(ok(a1,a2))
{
newnode(a1,p1);
newnode(a2,p2);
add(nodetop-1,nodetop-2,(a1-a2).len());
add(nodetop-2,nodetop-1,(a1-a2).len());
}
if(ok(b1,b2))
{
newnode(b1,p1);
newnode(b2,p2);
add(nodetop-1,nodetop-2,(b1-b2).len());
add(nodetop-2,nodetop-1,(b1-b2).len());
}
}
}
double dis[N*N*N];
double SPFA(int s,int t,int n)
{
bool flag[N*N*N]={};
for(int i=0;i<n;i++)dis[i]=1e30;
std::queue<int>Q;
Q.push(s);
dis[s]=0.0;
while(!Q.empty())
{
int x=Q.front();Q.pop();
flag[x]=false;
for(node *tmp=h[x].next;tmp;tmp=tmp->next)
if(dis[tmp->p]>dis[x]+tmp->c)
{
dis[tmp->p]=dis[x]+tmp->c;
if(!flag[tmp->p])flag[tmp->p]=true,Q.push(tmp->p);
}
}
return dis[t];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
nodetop=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf%lf",&C[i].x,&C[i].y,&R[i]);
for(int i=0;i<=n;i++)V[i].clear();
unit s(0,0),t(1000,1000);
if(ok(s,t))
{
printf("%.2lf\n",(t-s).len());
continue;
}
newnode(s,0);
newnode(t,0);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
calc(i,j);
for(int i=1;i<=n;i++)
{
unit a,b;
PtoC(s,C[i],R[i],a,b);
if(ok(s,a))
{
newnode(a,i);
add(0,nodetop-1,(s-a).len());
add(nodetop-1,0,(s-a).len());
}
if(ok(s,b))
{
newnode(b,i);
add(0,nodetop-1,(s-b).len());
add(nodetop-1,0,(s-b).len());
}
unit c,d;
PtoC(t,C[i],R[i],c,d);
if(ok(t,c))
{
newnode(c,i);
add(1,nodetop-1,(t-c).len());
add(nodetop-1,1,(t-c).len());
}
if(ok(t,d))
{
newnode(d,i);
add(1,nodetop-1,(t-d).len());
add(nodetop-1,1,(t-d).len());
}
}
for(int i=1;i<=n;i++)
PonC(V[i],C[i],R[i]);
printf("%.2lf\n",SPFA(0,1,nodetop));
}
}

記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2010高中組決賽
 NPSC 2010 高中組 決賽 G.