//Landmark //Author Hidetoshi Muta #include #include #include #include using namespace std; typedef complex cd; typedef pair line; //直線と線分の二重の意味の型なので注意 typedef vector polygon; //凸多角形全ての辺は反時計回りに並ぶ typedef vector group; #define EPS 1e-8 // cd 用エラー値、直線同士の交点が存在しないとき等の返り値として使用 #define ERRP cd(DBL_MAX, DBL_MAX) //直線l 上に点 p が存在すれば true bool onLine(const line& l, const cd& p){ return(abs(imag((p - l.first)/(l.second - l.first))) < EPS); } //直線l1 と 直線l2 が直線として一致すれば true bool equalLine(const line& l1, const line& l2){ return(onLine(l1, l2.first) && onLine(l1, l2.second)); } //線分s 上に 点p が存在するか? bool onSegment(const line& s, const cd& p){ cd rotate = (p - s.first)/(s.second - s.first); return(abs(imag(rotate)) < EPS && 0.0 - EPS <= real(rotate) && real(rotate) <= 1.0 + EPS); } //直線l1 と直線l2 の交点 //p1 + a * v1 = p2 + b * v2 を解いている(p:位置ベクトル(複素数)、v:方向ベクトル(複素数)、a,b:媒介変数(実数)) //p1 - p2 + a * v1 = b * v2 //両辺をv1 で割る //(p1 - p2)/v1 + a = b * v2/v1 //両辺の複素数部分をとる //imag((p1-p2)/v1) + imag(a) = imag(b*v2/v1) //a, b 実数より //imag((p1-p2)/v1) = b*imag(v2/v1) //imag(v2/v1) が非ゼロならば(平行ならば) //imag((p1-p2)/v1) / imag(v2/v1) = b cd crossPointLineAndLine(const line& l1, const line& l2){ cd p1 = l1.first; cd v1 = l1.second - l1.first; cd p2 = l2.first; cd v2 = l2.second - l2.first; double d1 = imag(v2/v1); if(abs(d1) < EPS)return(ERRP); double d2 = imag((p1-p2)/v1); double b = d2/d1; return(p2+b*v2); } //直線と線分の交点 cd crossPointLineAndSegment(const line& l, const line& s){ cd point = crossPointLineAndLine(l,s); if(point == ERRP)return(ERRP); if(onSegment(s, point))return(point); return(ERRP); } //多角形に線分を追加 void addEdge(polygon& poly, const line& l){ if(abs(l.first - l.second) < EPS)return; poly.push_back(l); } //凸多角形を直線で二分する group cut(const polygon& poly, const line& l){ group output; bool cutable = false; polygon poly1, poly2; cd crosspoint1 = ERRP; for(polygon::const_iterator it = poly.begin(); it != poly.end(); it++){ cd tempcrosspoint = crossPointLineAndSegment(l, *it); //容易に記述するために //多角形の辺の片方の端点と直線が交差する場合は無視する if(tempcrosspoint != ERRP && abs(tempcrosspoint - it->second) < EPS)tempcrosspoint = ERRP; if(tempcrosspoint == ERRP){ if(crosspoint1 == ERRP){ addEdge(poly1, *it); } else{ addEdge(poly2, *it); } } else{ //多角形と直線が最初に交差した場合 //it->first が poly1 側 //it->second が poly2 側 if(crosspoint1 == ERRP){ crosspoint1 = tempcrosspoint; addEdge(poly1, make_pair(it->first, crosspoint1)); addEdge(poly2, make_pair(crosspoint1, it->second)); } //多角形と直線が二度目に交差した場合 //it->first が poly2 側 //it->second が poly1 側 else{ cd crosspoint2 = tempcrosspoint; addEdge(poly2, make_pair(it->first, crosspoint2)); addEdge(poly2, make_pair(crosspoint2, crosspoint1)); addEdge(poly1, make_pair(crosspoint1, crosspoint2)); addEdge(poly1, make_pair(crosspoint2, it->second)); crosspoint1 = ERRP; cutable = true; } } } if(cutable){ //切れた場合 output.push_back(poly1); output.push_back(poly2); } else{ //二回交差しなかった場合は結局切れてはいないので無視して自身を追加する output.push_back(poly); } return(output); } //多角形の面積計算 double calArea(const polygon &p){ double sum = 0.0; for(polygon::const_iterator itline = p.begin(); itline != p.end(); itline++){ sum += imag(itline->second * conj(itline->first)); } return(0.5 * sum); } //点point から n個のランドマーク *p を見たとき //見える順序が入力で指定された orderstring 通りなら true //strstr(indexOf)が使われている理由は //123456 と 456123 が巡回を無視すれば一致するという処理を //123456 を二重化した文字列を使って //123456123456 から 456123 が部分文字列として含まれるかの判定で代用しているため bool matchorder(cd point, int n, const cd* p, const char* orderstring){ pair array[n]; for(int i = 0; i < n; i++){ array[i] = make_pair(arg(p[i] - point), i + 1); } sort(array, array + n); char temporderstring[n+1]; for(int i = 0; i < n; i++){ temporderstring[i] = array[i].second; } temporderstring[n] = '\0'; return(strstr(orderstring, temporderstring) != NULL); } //端を含むか bool isInf(const polygon& p, double xmax, double xmin, double ymax, double ymin){ for(polygon::const_iterator it = p.begin(); it != p.end(); it++){ if(real(it->first) == xmax || real(it->first) == xmin || imag(it->first) == ymax || imag(it->first) == ymin)return(true); } return(false); } int main(void){ int n; for(int counter = 1; cin >> n; counter++){ //入力 cd p[n]; char orderstring[21]; for(int i = 0; i < n; i++){ double x, y; cin >> x >> y; p[i] = cd(x, y); } for(int i = 0; i < n; i++){ int num; cin >> num; orderstring[i ] = num; orderstring[i+n] = num; } orderstring[2*n] = '\0'; //必要な直線集合の取得と //必要な bounding box の取得 vector lines; double xmax = -DBL_MAX; double xmin = DBL_MAX; double ymax = -DBL_MAX; double ymin = DBL_MAX; for(int i = 0; i < n; i++){ for(int j = i+1; j < n; j++){ line templine = make_pair(p[i], p[j]); bool alreadyexist = false; for(vector::iterator it = lines.begin(); it != lines.end(); it++){ if(equalLine(templine, *it)){ alreadyexist = true; break; } cd point = crossPointLineAndLine(templine, *it); if(point != ERRP){ xmax = max(xmax, real(point) + 1.0); xmin = min(xmin, real(point) - 1.0); ymax = max(ymax, imag(point) + 1.0); ymin = min(ymin, imag(point) - 1.0); } } if(!alreadyexist)lines.push_back(templine); } } //全直線で bounding box の分割 polygon initpolygon; group prevgroup; initpolygon.push_back(make_pair(cd(xmin, ymin), cd(xmax, ymin))); initpolygon.push_back(make_pair(cd(xmax, ymin), cd(xmax, ymax))); initpolygon.push_back(make_pair(cd(xmax, ymax), cd(xmin, ymax))); initpolygon.push_back(make_pair(cd(xmin, ymax), cd(xmin, ymin))); prevgroup.push_back(initpolygon); for(vector::iterator itline = lines.begin(); itline != lines.end(); itline++){ group nextgroup; for(group::iterator itarea = prevgroup.begin(); itarea != prevgroup.end(); itarea++){ group newgroup = cut(*itarea, *itline); for(group::iterator it = newgroup.begin(); it != newgroup.end(); it++){ nextgroup.push_back(*it); } } prevgroup = nextgroup; } //領域計算 bool noarea = true; bool inf = false; double areasum = 0.0; for(group::iterator itpoly = prevgroup.begin(); itpoly != prevgroup.end(); itpoly++){ cd innerPoint = ((*itpoly)[0].first + (*itpoly)[1].first + (*itpoly)[2].first)/3.0; if(matchorder(innerPoint, n, p, orderstring)){ noarea = false; areasum += calArea(*itpoly); if(isInf(*itpoly, xmax, xmin, ymax, ymin)){ inf = true; break; } } } //出力 if(noarea){ printf("Case %d: No area\n", counter); } else if(inf){ printf("Case %d: Infinity\n", counter); } else{ printf("Case %d: %.20f\n", counter, areasum); } } return(0); }