AOJ0090 Overlaps of Seals
やるだけ埋めの最中に楽しみが生えたので書きます。
直交座標すると結構面倒なやつが競プロだとarccosとかが使えるために代わりに回転で表現できて複素座標最強になるのを実感したのでコード張ります。結構いい感じになってる気がする。
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> #include<math.h> #include<stdlib.h> using namespace std; typedef pair<double,double>pdd; double eps=1e-9; pdd rotate(pdd a,double arg) { return make_pair(a.first*cos(arg)-a.second*sin(arg),a.first*sin(arg)+a.second*cos(arg)); } double len(pdd a) { return sqrt((a.first*a.first)+(a.second*a.second)); } pdd tot(pdd a) { return make_pair(a.first/len(a),a.second/len(a)); } pdd pls(pdd a,pdd b) { return make_pair(a.first+b.first,a.second+b.second); } int main() { for(;;) { int num; scanf("%d",&num); if(num==0)return 0; vector<pdd>vec; for(int i=0;i<num;i++) { double za,zb; scanf("%lf,%lf",&za,&zb); vec.push_back(make_pair(za,zb)); } int maxi=1; for(int i=0;i<vec.size();i++) { for(int j=0;j<vec.size();j++) { if(i==j)continue; pdd v=make_pair(vec[i].first-vec[j].first,vec[i].second-vec[j].second); if(len(v)>2.0+eps)continue; double arg=acos(len(v)/2.0); pdd ka=pls(tot(rotate(v,arg)),vec[j]); pdd kb=pls(tot(rotate(v,-arg)),vec[j]); int ca=0; for(int k=0;k<vec.size();k++) { if(len(make_pair(ka.first-vec[k].first,ka.second-vec[k].second))<1.0+eps)ca++; } int cb=0; for(int k=0;k<vec.size();k++) { if(len(make_pair(kb.first-vec[k].first,kb.second-vec[k].second))<1.0+eps)cb++; } maxi=max(maxi,max(ca,cb)); } } printf("%d\n",maxi); } }
一番面倒な円同士の交点をとるパートがきれいにかけてる(自画自賛)
あと幾何はほとんどやったことがないのでこれは汎用テクかもしれない(というかそうだと思う)