AOJ 0090: Overlaps of Seals
苦労しました...
この問題は、随分前から様々なアルゴリズムを考えていましたが、漸く通すことが出来ました...
"シールの重なり"と捉えるとなかなか難しい所がありますね.
この問題は、随分前から様々なアルゴリズムを考えていましたが、漸く通すことが出来ました...
"シールの重なり"と捉えるとなかなか難しい所がありますね.
#include <stdio.h> #include <math.h> #define SQ(x) ((x) * (x)) #define EPS 1e-5 typedef struct { double x; double y; } POINT; int dist(POINT a, POINT b, double d) { if (sqrt(SQ(a.x - b.x) + SQ(a.y - b.y)) - d > EPS){ return (0); } return (1); } int max(int a, int b) { if (a > b){ return (a); } return (b); } int main(void) { POINT seal[100], v; static POINT l[300000]; int s; double a, a0, d, t; int n; int count, ans; int i, j, k; while (1){ scanf("%d", &n); if (!n){ break; } for (i = 0; i < n; i++){ scanf("%lf%*c%lf", &seal[i].x, &seal[i].y); } s = 0; for (i = 0; i < n; i++){ for (j = 0; j < n; j++){ if (dist(seal[i], seal[j], 2) && i != j){ //2つの円の交点を求める(一番苦労しました) d = sqrt(SQ(seal[i].x - seal[j].x) + SQ(seal[i].y - seal[j].y)); a = atan2(seal[j].y - seal[i].y, seal[j].x - seal[i].x); a0 = acos(0.5 * d); l[s].x = seal[i].x + cos(a0 + a); l[s].y = seal[i].y + sin(a0 + a); s++; l[s].x = seal[i].x + cos(a0 - a); l[s].y = seal[i].y + sin(a0 - a); s++; } } } ans = 1; for (i = 0; i < s; i++){ count = 0; for (j = 0; j < n; j++){ if (dist(seal[j], l[i], 1)){ count++; } } ans = max(ans, count); } printf("%d\n", ans); } return (0); }
2011-12-11 23:42
nice!(0)
コメント(0)
トラックバック(0)
コメント 0