学步园

同2167，只不过这次不是单位圆覆盖了，是给定半径了，方法都一样，比2167规模大不少。

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define BUG puts("here!!!")
#define STOP system("pause")

using namespace std;

const int MAX = 4010;
struct point {double x,y;};
struct NODE { double t; int id, flag;};
point p[MAX];
NODE t[MAX];
double r;
const double eps = 1e-6;
bool dy(double x,double y)	{	return x > y + eps;}	// x > y 
bool xy(double x,double y)	{	return x < y - eps;}	// x < y 
bool dyd(double x,double y)	{ 	return x > y - eps;}	// x >= y 
bool xyd(double x,double y)	{	return x < y + eps;} 	// x <= y 
bool dd(double x,double y) 	{	return fabs( x - y ) < eps;}  // x == y
double disp2p(point a,point b) //  a b 两点之间的距离 
{
	return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );
}
point l2l_inst_p(point u1,point u2,point v1,point v2)
{
	point ans = u1;
	double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x))/
				((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x));
	ans.x += (u2.x - u1.x)*t;
	ans.y += (u2.y - u1.y)*t;
	return ans;
}
void l2c_inst_p(point c,double r,point l1,point l2,point &p1,point &p2)
{
	point p = c;
	double t;
	p.x += l1.y - l2.y;
	p.y += l2.x - l1.x;
	p = l2l_inst_p(p,c,l1,l2);
	t = sqrt(r*r - disp2p(p,c)*disp2p(p,c))/disp2p(l1,l2);
	p1.x = p.x + (l2.x - l1.x)*t;
	p1.y = p.y + (l2.y - l1.y)*t;
	p2.x = p.x - (l2.x - l1.x)*t;
	p2.y = p.y - (l2.y - l1.y)*t;
}
void c2c_inst_p(point c1,double r1,point c2,double r2,point &p1,point &p2)
{
	point u,v;
	double t;
	t = (1 + (r1*r1 - r2*r2)/disp2p(c1,c2)/disp2p(c1,c2))/2;
	u.x = c1.x + (c2.x - c1.x)*t;
	u.y = c1.y + (c2.y - c1.y)*t;
	v.x = u.x + c1.y - c2.y;
	v.y = u.y - c1.x + c2.x;
	l2c_inst_p(c1,r1,u,v,p1,p2);
}
bool cmp(NODE a,NODE b)
{
	if( a.t == b.t ) return a.flag > b.flag;
	return xy(a.t, b.t);
}
double disp2p_sqr(point a,point b)
{
	return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
int solve(int n)
{
	int maxx = 1, cnt;
	bool ind[MAX]; 
	for(int i=0; i<n; i++)
	{
		cnt = 0;
		for(int k=0; k<n; k++)
		{
			if( i == k ) continue;
			if( disp2p_sqr(p[i], p[k]) > 4*r*r ) continue;
			point a,b;
			c2c_inst_p(p[i], r, p[k], r, a, b);//求得 两圆的交点，注意交点方向性，确定是标记1还是-1 
			t[cnt].id = k;
			t[cnt].flag = -1;
			t[cnt++].t = atan2(a.y - p[i].y, a.x - p[i].x);
			
			t[cnt].id = k;
			t[cnt].flag = 1;
			t[cnt++].t = atan2(b.y - p[i].y, b.x - p[i].x);
		}
		
		if( cnt == 0 ) continue;
		
		sort(t, t+cnt, cmp);
		memset(ind, false, sizeof(ind));
		
		int s = 0, sum = 1, j = 0;
		while( s < cnt/2 )
		{
			if( t[j].flag > 0 )
			{
				sum++;
				if( sum > maxx )
					maxx = sum;
				ind[t[j].id] = true;	// 标记已经进入了 
			}
			else
				if( ind[t[j].id] == true )	// 如果遇到出的点，而且进过，那么就走过了一个完整的弧，标记下 
				{
					s++;
					sum--;
				}	
			j++; j %= cnt;
		}
	}
	return maxx;		
}

int main()
{
	int n;

	while( ~scanf("%d", &n) && n )
	{
		scanf("%lf", &r);
		
		for(int i=0; i<n; i++)
			scanf("%lf%lf", &p[i].x, &p[i].y);
		
		int ans = solve(n);
		
		if( ans == 0 )
			ans = 1;
			
		printf("It is possible to cover %d points.\n", ans);

	}

return 0;
}