#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; static const double EPS = 1e-8; static const double PI = 4.0 * atan(1.0); static const double PI2 = 8.0 * atan(1.0); typedef long long ll; #define REP(i,n) for(int i=0;i<(int)n;++i) #define ALL(c) (c).begin(), (c).end() typedef complex P; //#define DEBUG //#undef DEBUG //#define VISUALIZE //#undef VISUALIZE #ifdef VISUALIZE #include static const string filePath = "immortal.nodchip.mp"; // 紙面上の表示位置 static const double kLeft = 10.0; static const double kBottom = 10.0; static const double kSize = 500.0; class Drawer { public: Drawer() : file(NULL) { } void open() { file = fopen(filePath.c_str(), "at"); }; void close() { fclose(file); file = NULL; } void registerCircle(double x, double y, double r, const string& width = "1", const string& color = "black") { objects.push_back(boost::shared_ptr(new Circle(x, y, r, width, color))); } void registerSegment(double x0, double y0, double x1, double y1, const string& width = "1", const string& color = "black") { objects.push_back(boost::shared_ptr(new Segment(x0, y0, x1, y1, width, color))); } void draw() const { double minX = 1e10; double maxX = -1e10; double minY = 1e10; double maxY = -1e10; for (vector >::const_iterator it = objects.begin(), itEnd = objects.end(); it != itEnd; ++it) { const Object& object = **it; object.minMax(minX, maxX, minY, maxY); } const double length = max(maxX - minX, maxY - minY); const double dx = (length - (maxX - minX)) * 0.5; const double dy = (length - (maxY - minY)) * 0.5; minX -= dx; maxX += dx; minY -= dy; maxY += dy; for (vector >::const_iterator it = objects.begin(), itEnd = objects.end(); it != itEnd; ++it) { const Object& object = **it; object.draw(file, minX, maxX, minY, maxY); } } private: class Object { public: Object(const string& width, const string& color) : width(width), color(color) { } virtual void minMax(double& minX, double& maxX, double& minY, double& maxY) const = 0; virtual void draw(FILE* file, double minX, double maxX, double minY, double maxY) const = 0; protected: double scale(double value, double minValue, double maxValue, double offset, double size) const { double vv = (value - minValue) / (maxValue - minValue); double vvv = vv * size + offset; return vvv; } double scale(double value, double scaling, double size) const { return value / scaling * size; } string width; string color; }; class Segment : public Object { public: Segment(double x0, double y0, double x1, double y1, const string& width, const string& height) : Object(width, height), x0(x0), y0(y0), x1(x1), y1(y1) { } void minMax(double& minX, double& maxX, double& minY, double& maxY) const { minX = min(minX, x0); minX = min(minX, x1); maxX = max(maxX, x0); maxX = max(maxX, x1); minY = min(minY, y0); minY = min(minY, y1); maxY = max(maxY, y0); maxY = max(maxY, y1); } void draw(FILE* file, double minX, double maxX, double minY, double maxY) const { const double x0a = x0 + 5.0 * (x0 - x1); const double y0a = y0 + 5.0 * (y0 - y1); const double x1a = x1 + 5.0 * (x1 - x0); const double y1a = y1 + 5.0 * (y1 - y0); fprintf(file, "draw (%f, %f) -- (%f, %f) withpen pencircle scaled %sbp withcolor %s;\n", scale(x0a, minX, maxX, kLeft, kSize), scale(y0a, minY, maxY, kLeft, kSize), scale(x1a, minX, maxX, kLeft, kSize), scale(y1a, minY, maxY, kLeft, kSize), width.c_str(), color.c_str()); } private: double x0, y0, x1, y1; }; class Circle : public Object { public: Circle(double x, double y, double r, const string& width, const string& color) : Object(width, color), x(x), y(y), r(r) { } void minMax(double& minX, double& maxX, double& minY, double& maxY) const { minX = min(minX, x - r); maxX = max(maxX, x + r); minY = min(minY, y - r); maxY = max(maxY, y + r); } void draw(FILE* file, double minX, double maxX, double minY, double maxY) const { const double scaling = max(maxX - minX, maxY - minY); fprintf(file, "draw fullcircle scaled %f shifted (%f, %f) withpen pencircle scaled %sbp withcolor %s;\n", scale(r, scaling, kSize) * 2.0, scale(x, minX, maxX, kLeft, kSize), scale(y, minY, maxY, kBottom, kSize), width.c_str(), color.c_str()); } private: double x, y, r; }; vector > objects; FILE* file; }; #endif //円(x0,y0,r0)と円(x1,y1,r1)の共通接線の接点 void tangency(double x0, double y0, double r0, double x1, double y1, double r1, pair out[4]) { const P v(x1 - x0, y1 - y0); const double a0 = arg(v); const double a1 = acos((r0 - r1) / abs(v)); out[0] = make_pair(P(x0 + r0 * cos(a0 + a1), y0 + r0 * sin(a0 + a1)), P(x1 + r1 * cos(a0 + a1), y1 + r1 * sin(a0 + a1))); out[1] = make_pair(P(x0 + r0 * cos(a0 - a1), y0 + r0 * sin(a0 - a1)), P(x1 + r1 * cos(a0 - a1), y1 + r1 * sin(a0 - a1))); const double a2 = acos((r0 + r1) / abs(v)); out[2] = make_pair(P(x0 + r0 * cos(a0 + a2), y0 + r0 * sin(a0 + a2)), P(x1 + r1 * cos(a0 + a2 + PI), y1 + r1 * sin(a0 + a2 + PI))); out[3] = make_pair(P(x0 + r0 * cos(a0 - a2), y0 + r0 * sin(a0 - a2)), P(x1 + r1 * cos(a0 - a2 + PI), y1 + r1 * sin(a0 - a2 + PI))); } struct Jewel { P p; double r, m; }; // 外積 double cross(const P& a, const P& b) { return a.real() * b.imag() - a.imag() * b.real(); } // 点と直線の距離 // wataライブラリより // 外積を使ってベクトルp1->p2とベクトルp1->qのなす平行四辺形の面積を計算した後 // 底辺で割って高さを出している double disLP(const P& p1, const P& p2, const P& q) { return abs(cross(p2 - p1, q - p1)) / abs(p2 - p1); } #ifdef DEBUG vector hits; #endif int solve(const P& p1, const P& p2, const vector& jewels) { #ifdef DEBUG hits.clear(); #endif int result = 0; for (vector::const_iterator it = jewels.begin(), itEnd = jewels.end(); it != itEnd; ++it) { const double d = disLP(p1, p2, it->p); if (it->r - EPS < d && d < it->r + it->m + EPS) { ++result; #ifdef DEBUG hits.push_back(*it); #endif } } return result; } int main() { for (int N; cin >> N && N; ) { #ifdef VISUALIZE Drawer drawer; drawer.open(); drawer.registerSegment(-10, 0, 10, 0); drawer.registerSegment(0, -10, 0, 10); #endif vector jewels; REP(i, N) { double x, y, r, m; cin >> x >> y >> r >> m; Jewel jewel; jewel.p = P(x, y); jewel.r = r; jewel.m = m; jewels.push_back(jewel); #ifdef VISUALIZE drawer.registerCircle(x, y, r, "1", "red"); drawer.registerCircle(x, y, r + m, "1", "green"); #endif } if (N == 1) { #ifdef VISUALIZE drawer.draw(); drawer.close(); #endif cout << 1 << endl; continue; } #ifdef VISUALIZE P segmentBegin; P segmentEnd; #endif #ifdef DEBUG P segmentBegn; P segmentEnd; vector hitJewels; #endif int bestAnswer = 0; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { const Jewel& a = jewels[i]; const Jewel& b = jewels[j]; const double ar[2] = {a.r, a.r + a.m}; const double br[2] = {b.r, b.r + b.m}; REP(k, 2) { REP(l, 2) { pair tangents[4]; tangency(a.p.real(), a.p.imag(), ar[k], b.p.real(), b.p.imag(), br[l], tangents); REP(m, 4) { const int answer = solve(tangents[m].first, tangents[m].second, jewels); if (bestAnswer < answer) { bestAnswer = answer; #ifdef VISUALIZE segmentBegin = tangents[m].first; segmentEnd = tangents[m].second; #endif #ifdef DEBUG segmentBegn = tangents[m].first; segmentEnd = tangents[m].second; hitJewels = hits; #endif } } } } } } #ifdef VISUALIZE drawer.registerSegment(segmentBegin.real(), segmentBegin.imag(), segmentEnd.real(), segmentEnd.imag(), "1", "blue"); drawer.draw(); drawer.close(); #endif #ifdef DEBUG cout << segmentBegn << "-" << segmentEnd << endl; for (vector::iterator it = hitJewels.begin(), itEnd = hitJewels.end(); it != itEnd; ++it) { cout << it->p << " " << it->r << " " << it->r + it->m << endl; } #endif cout << bestAnswer << endl; } }