//2007年国内予選E問題 //牟田秀俊 #include #include #include using namespace std; typedef complex cd; typedef pair edge; #define EPS 1e-8 #define PI 3.14159265358979323846 double sign[] = {1.0, -1.0}; //交差判定 //p0 + a0 * v0 = p1 + a1 * v1 //交差する場合は a0 の値 0以上1以下 //交差しない場合は -1 double cross(cd p0, cd v0, cd p1, cd v1){ if(abs(imag(v1/v0)) < EPS)return(-1.0); double a0 = -imag((p0 - p1) / v1) / imag(v0/v1); double a1 = imag((p0 - p1) / v0) / imag(v1/v0); if(a0 < -EPS || 1.0 + EPS < a0 || a1 < -EPS || 1.0 + EPS < a1)return(-1.0); return(a0); } //point が 線分 p0 - p1 上にあるかどうか? //p0 が 0+0i に p1 が 1+0i に移動するように平行、point を回転縮小移動 //移動後の point が実軸上 0 - 1 の間にあれば線分上にある bool online(cd point, cd p0, cd p1){ point -= p0; p1 -= p0; point /= p1; return(abs(imag(point)) < EPS && -EPS < real(point) && real(point) < 1.0 + EPS); } //多角形の辺上に point があるか? bool onlineGroup(cd point, cd *p, int n){ for(int i = 0; i < n; i++){ if(online(point, p[i], p[i+1]))return(true); } return(false); } //point が非凸な多角形の内点かどうかの判定 //point から伸ばした半直線と多角形の辺との交点の個数が奇数ならば内部 //半直線の方向は乱数決定、ちょうど辺の端点を通って二重数え上げが疑われる場合は再実行 bool inside(cd point, cd *p, int n){ if(onlineGroup(point, p, n))return(true); int count; bool retry; do{ double arg = 2.0 * PI * rand() / RAND_MAX; cd outside = cd(2000 * cos(arg), 2000 * sin(arg)); retry = false; count = 0; for(int i = 0; i < n; i++){ double rate = cross(p[i], p[i+1] - p[i], point, outside - point); if(abs(rate - 0.0) < EPS || abs(rate - 1.0) < EPS){ retry = true; break; } if(rate >= 0.0)count++; } }while(retry); return(count % 2 == 1); } //回転後の線分a b が多角形の内部にあるか //線分と多角形の辺が交差する点を全列挙しソートして //隣接する交差した点の中点に関して内点判定を行う bool valid(cd a, cd b, cd *p, int n){ vector rate; rate.push_back(0.0); rate.push_back(1.0); cd p0 = a; cd v0 = b - a; for(int i = 0; i < n; i++){ cd p1 = p[i]; cd v1 = p[i+1] - p[i]; double r = cross(p0, v0, p1, v1); if(r < -EPS)continue; rate.push_back(r); } sort(rate.begin(), rate.end()); for(int i = 1; i < rate.size(); i++){ double ravg = 0.5 * (rate[i-1] + rate[i]); cd point = p0 + ravg * v0; if(!inside(point, p, n))return(false); } return(true); } //角度を [-PI , PI] に正規化(超手抜き) double normalizeArgument(double argument){ return(atan2(sin(argument), cos(argument))); } //oldArg から newArg に反時計周りにどれだけ回転させればいいか double diff(double oldArg, double newArg){ if(abs(oldArg - newArg) < EPS)return(0.0); if(abs(abs(oldArg) - PI) < EPS && abs(abs(newArg) - PI) < EPS)return(0.0); if(oldArg > newArg)return(oldArg - newArg); return(2*PI + oldArg - newArg); } //c を端点とする長さ r の線分が [p0, p1] の線分と衝突する角度を列挙 //c を中心とする半径 r の円と線分との交点 //c を中心とする半径 r の円の内部に線分の端点がある vector crossArg(cd c, cd p0, cd p1, double r){ //とりあえずp0 を原点 p1 を実軸上、実成分が正へ平行&回転移動 p1 -= p0; c -= p0; double len = abs(p1); cd normp1 = p1 / len; c /= normp1; //c を中心とする半径 r の円と線分との交点 double y = imag(c); vector output; if(abs(y) < r){ for(int i = 0; i < 2; i++){ double xvalue = real(c) + sign[i] * sqrt(r*r - y*y); if(0 <= xvalue && xvalue <= len){ cd v = cd(xvalue, 0) - c; //出力前に回転を戻す v *= normp1; output.push_back(arg(v)); } } } //c を中心とする半径 r の円の内部に線分の端点がある for(int i = 0; i < 2; i++){ //p0 or p1 cd p = cd(len * i, 0.0); cd v = p - c; if(abs(v) < r){ v *= normp1; output.push_back(arg(v)); } } return(output); } int main(void){ double l, r; int n; cd p[200]; cd center; double argument; double alen; while(true){ cin >> l >> r >> n; if(n == 0)break; //入力 for(int i = 0; i < n; i++){ double x, y; cin >> x >> y; p[i] = cd(x, y); } p[n] = p[0]; //初期値 center = cd(0.0, 0.0); alen = 0.0; argument = -0.5 * PI; r *= 2.0 * PI; //メイン処理 cd a, b, v; while(r > EPS){ //特徴角列挙 vector arglist; arglist.push_back(0.0); double radius[] = {alen, l - alen}; double argumentarray[] = {argument, normalizeArgument(argument + PI)}; for(int i = 0; i < n; i++){ for(int j = 0; j < 2; j++){ vector vec = crossArg(center, p[i], p[i+1], radius[j]); for(vector::iterator it = vec.begin(); it != vec.end(); it++){ arglist.push_back(diff(argumentarray[j], *it)); } } } //特徴角の中でどこまで回転できるか探索 //特徴角をソート //隣接する特徴角の平均値において回転移動後の線分が条件を満たすかチェック sort(arglist.begin(), arglist.end()); for(int i = 1; i < arglist.size(); i++){ double rot0 = arglist[i-1]; double rot1 = arglist[i]; double avg = 0.5 * (rot0 + rot1); v = cd(cos(argument - avg), sin(argument - avg)); a = center + alen * v; b = center - (l - alen) * v; if(valid(a, b, p, n)){ //next } else if(rot0 < EPS){ //can not rotate r = -1.0; break; } else{ if(rot0 < r){ argument -= rot0; r -= rot0; } else{ argument -= r; r = -1.0; } break; } if(i == arglist.size() -1){ r -= rot1; argument -= rot1; } } argument = normalizeArgument(argument); //次の回転の中心を探索 v = cd(cos(argument), sin(argument)); a = center + alen * v; b = center - (l - alen) * v; if(abs(a - center) > EPS && onlineGroup(a, p, n)){ center = a; } else if(abs(b - center) > EPS && onlineGroup(b, p, n)){ center = b; } else{ //両端点が多角形と接しない場合、 //現在の回転の中心から最も遠い、線分が多角形と共有する点を次の回転の中心とする //現在の回転の中心の両側に共有点がある場合、どうせこれ以上回転できないので気にしない double centerrate = alen / l; double nextCenterRate = centerrate; for(int i = 0; i < n; i++){ double rate = cross(a, b-a, p[i], p[i+1]-p[i]); if(rate < -EPS)continue; if(abs(rate - centerrate) > abs(nextCenterRate - centerrate)){ nextCenterRate = rate; } } center = a + (b-a) * nextCenterRate; } //新しい中心から頂点Aの距離を再計算 alen = abs(a - center); } printf("%.10f %.10f\n", real(a), imag(a)); } }