円の交点座標を求めてその点を含んでいる円の数をカウントすればいいんだけど、
円の交点座標を求めるのがなかなか大変。三角関数とかベクトルを使わないと恐ろしいことになるっぽい。
ということで、
を見つつ交点を出力する関数をつくる。一つ目の落とし穴はC言語のatan2は引数がy,xの順番で与えられていること。
二つの目の落とし穴は、解法は恐らくあってるはずなのに、ひたすらWAしか出ないなーと思っていたら『最大値記憶用変数を1で初期化していなかった』(他人に言われて気づいたorz)
WA10回くらい出しましたごめんなさい。
#include <iostream> #include <vector> #include <cmath> #include <cstdio> using namespace std; struct P{double x,y;}; #define rep(i,n) for(int i=0;i<n;i++) const double EPS = 1e-15; vector<P> cross(P a, P b){ vector<P> ret; double x = a.x - b.x , y = a.y - b.y; double L = x * x + y * y; if(L > 4.0)return ret; L = sqrt(L); double C = atan2(b.y-a.y,b.x-a.x); double alpha = acos(L/2); P r1,r2; r1.x = a.x + cos(C+alpha) , r1.y = a.y + sin(C+alpha); r2.x = a.x + cos(C-alpha) , r2.y = a.y + sin(C-alpha); ret.push_back(r1) , ret.push_back(r2); return ret; } bool check(P cir , P pt){ cir.x -= pt.x , cir.y -= pt.y; return (cir.x*cir.x + cir.y * cir.y) <= 1.0 + EPS; } int main(){ int n; while(scanf("%d",&n) && n){ int ret = 1; vector<P> data(n); rep(i,n)scanf("%lf,%lf\n",&data[i].x,&data[i].y); vector<P> search; rep(i,n){ for(int j=i+1;j<n;j++){ vector<P> get = cross(data[i],data[j]); rep(k,get.size())search.push_back(get[k]); } } rep(i,search.size()){ int count = 0; rep(j,n)count += check(data[j],search[i]); ret = max(ret,count); } cout << ret << endl; } }