列表

详情

NC15935. Rectangle

描述

There is a rectangular area in 2 dimensional Cartesian coordinate system. Its width is w, height is h and left bottom point is (0,0). A circle and some key points are in this area. In the area (including the boundary), point A is visible to B if and only if the segment AB doesn’t intersect with the circle (As a special case, A is visible to B if the segment is tangent to the Circle). Now you can choose a point P in the area (this point doesn’t need to be key points, it can be any point in the area including the boundary points). Let k denote the number of key points that are visible to P. Your task is to calculate the maximum k.

输入描述

The first line is an integer T, representing the
number of test cases.

For each test case:

The first line are two integers h, w, denoting the
width and height of the rectangular area.

The second line are three integers r,cx,cy,
representing the radius of the circle and the position of the center.

The third line is an integer n, denoting the number
of key points.
n<=10000
Then n lines follow. Each line contains two integer xI,yI, representing
the position of the ith key point.

It is guaranteed that the circle is inside the
rectangular area (possibly tangent to the boundary), and all key points are
inside the area but outside the circle.

输出描述

For each test case, output the maximum number of
visible key points.

示例1

输入: 

2
65 51
2 15 7
6
42 42
22 42
46 13
16 44
29 12
19 29
20 20
4 14 10
4
7 13
3 9
1 1
15 4

输出: 

6
4

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 520ms, 内存消耗: 3820K, 提交时间: 2018-07-17 01:12:42 

#include<bits/stdc++.h>
//#include<cstdio>
//#include<cmath>
//#include<algorithm>
using namespace std;
typedef long double lod; //long long 或者long double
typedef long long ll;
typedef long double ld;
const ld eps=1e-3;
const ld pi=acos(-1.0);
int sgn(ld x)
{
    if (x<-eps) return -1;
    if (x>eps) return 1;
    return 0;
}

struct P; //点，向量
struct LINE; //线段，射线，直线;
struct CIRCLE;

void kr(ld &x)
{
    double t; scanf("%lf",&t);
    x=t;
}
void kr(ll &x)
{
    scanf("%lld",&x);
}
struct P
{
    lod x,y;
    lod val;
    int id;
    void read()
    {
        kr(x); kr(y);
    }
    P operator+(const P &t)const
    {
        return {x+t.x,y+t.y};
    }
    P operator-(const P &t)const
    {
        return {x-t.x,y-t.y};
    }
    P operator*(ld t)const
    {
        return {x*t,y*t};
    }
    P operator/(ld t)const
    {
        return {x/t,y/t};
    }
    lod operator*(const P &t)const
    {
        return x*t.y-y*t.x;
    } //叉积
    lod operator%(const P &t)const
    {
        return x*t.x+y*t.y;
    } //点积
    bool operator<(const P &t)const
    {
        return sgn(x-t.x)<0||sgn(x-t.x)==0&&sgn(y-t.y)<0;
    }
    bool operator==(const P &t)const
    {
        return sgn(x-t.x)==0&&sgn(y-t.y)==0;
    }
    ld ang()const
    {
        return atan2(y,x);
    }
    ld length()const
    {
        return sqrt(x*x+y*y);
    }
    P rotate(const P &t,ld sita)const
    {
        return {(x-t.x)*cos(sita)-(y-t.y)*sin(sita)+t.x,
                (x-t.x)*sin(sita)+(y-t.y)*cos(sita)+t.y};
    } //逆时针转sita
    ld btang(const P &t)const
    {
        return acos( (*this%t)/length()/t.length() );
    } //向量夹角
    P midvec(const P &t)const
    {
        return (*this)/length()+t/t.length();
    } //角平分向量
};

struct LINE
{
    P p1,p2;
    void read()
    {
        p1.read(); p2.read();
    }
	lod length()const{
		return (p2-p1).length();
	}
    LINE midLINE()
    {
        P midp=(p1+p2)/2;
        P v=p2-p1;
        v=v.rotate({0,0},pi/2);
        return {midp,midp+v};
    } //中垂线
    bool have1(const P &p)const
    {
        return sgn( (p-p1)*(p-p2) )==0&&sgn( (p-p1)%(p-p2) )<=0;
    } //线段上有点
    bool have2(const P &p)const
    {
        return sgn( (p-p1)*(p-p2) )==0&&sgn( (p-p1)%(p2-p1) )>=0;
    } //射线上有点
    bool have3(const P &p)const
    {
        return sgn( (p-p1)*(p-p2) )==0;
    } //直线上有点
    lod areawith(const P &p)const
    {
        return abs( (p1-p)*(p2-p)/2 );
    } //线段和点围成面积
    P vecfrom(const P &p)const
    {
        P v=(p2-p1);
        v=v.rotate({0,0},pi/2);
        ld s1=(p1-p)*(p2-p);
        ld s2=v*(p2-p1);
        v=v*(s1/s2);
        return v;
    }//点到直线垂足的向量
    P footfrom(const P &p)const
    {
        P v=vecfrom(p);
        return p+v;
    } //点到直线垂足
    ld dis1from(const P &p)const
    {
        P foot=footfrom(p);
        if (have1(foot)) return (foot-p).length();
        return min( (p1-p).length(),(p2-p).length());
    }//点到线段距离
    ld dis2from(const P &p)const
    {
        P foot=footfrom(p);
        if (have2(foot)) return (foot-p).length();
        return (p1-p).length();
    }//点到射线距离
    ld dis3from(const P &p)const
    {
        return vecfrom(p).length();
    }//点到直线距离
    P symP(const P &p)const
    {
        P v=vecfrom(p);
        return p+v*2;
    } //点关于直线的对称点


    bool parallel(const LINE &L)const{
        return sgn( (p2-p1)*(L.p2-L.p1) )==0;
    }
    //1线段 2射线 3直线
    bool isct11(const LINE &L)const
    {
        P a1=p1,a2=p2;
        P b1=L.p1,b2=L.p2;
        if (sgn( max(a1.x,a2.x)-min(b1.x,b2.x) )<0||
            sgn( max(b1.x,b2.x)-min(a1.x,a2.x) )<0||
            sgn( max(a1.y,a2.y)-min(b1.y,b2.y) )<0||
            sgn( max(b1.y,b2.y)-min(a1.y,a2.y) )<0)
                return 0;
        lod tmp1=(a2-a1)*(b1-a1);
        lod tmp2=(a2-a1)*(b2-a1);
        if (sgn(tmp1)<0&&sgn(tmp2)<0||sgn(tmp1)>0&&sgn(tmp2)>0) return 0;
        tmp1=(b2-b1)*(a1-b1);
        tmp2=(b2-b1)*(a2-b1);
        if (sgn(tmp1)<0&&sgn(tmp2)<0||sgn(tmp1)>0&&sgn(tmp2)>0) return 0;
        return 1;
    }
    bool isct21(const LINE &L)const
    {
        P v=p2-p1;
        P a=p1;
        P b1=L.p1,b2=L.p2;
        lod tmp1=v*(b1-a);
        lod tmp2=v*(b2-a);
        if (sgn(tmp1)<0&&sgn(tmp2)<0||sgn(tmp1)>0&&sgn(tmp2)>0) return 0;
        if (tmp1>tmp2) swap(b1,b2);
        if (sgn( (b1-a)*(b2-a) )>0) return 1;
        if (sgn( (b1-a)*(b2-a) )<0) return 0;
        //最后排除共线但不相交的情况
        return L.have1(a)||have2(b1)||have2(b2);
    }
    bool isct31(const LINE &L)const
    {
        P v=p2-p1;
        P a=p1;
        lod tmp1=v*(L.p1-a);
        lod tmp2=v*(L.p2-a);
        if (sgn(tmp1)<0&&sgn(tmp2)<0||sgn(tmp1)>0&&sgn(tmp2)>0) return 0;
        return 1;
    }
    bool isct22(const LINE &L)const
    {
        if (have2(L.p1)||L.have2(p1)) return 1;
        P v=vecfrom(L.p1);
        if (sgn( v%(L.p2-L.p1) )<=0) return 0;
        v=L.vecfrom(p1);
        if (sgn( v%(p2-p1) )<=0) return 0;
        return 1;
    }
    bool isct32(const LINE &L)const
    {
        if (have3(L.p1)) return 1;
        P v=vecfrom(L.p1);
        if (sgn( v%(L.p2-L.p1) )<=0) return 0;
        return 1;
    }
    bool isct33(const LINE &L)const
    {
        if (have3(L.p1)) return 1;
        return sgn( (p2-p1)*(L.p2-L.p1) )!=0;
    }

    //前提是不重合且有交点,p1沿p2-p1方向到达L上的长度，负数表示反向
    //直线交多边形需要用到
    ld dis33(const LINE &L)const
    {
        return (L.p1-p1)*(L.p2-p1) / ( (p2-p1)*(L.p2-L.p1) )
                * (p2-p1).length();
    }
    P isctPoint(const LINE &L)const
    {
        ld len=dis33(L);
        P v=p2-p1;
        return p1+v*(len/v.length());
    }//直线交点坐标

};

struct CIRCLE
{
    P cent;
    lod r;
    void read()
    {
        cent.read(); kr(r);
    }
    ld area()const
    {
        return pi*r*r;
    }
    bool have(const P &p)const
    {
        return sgn( (p-cent).length()-r ) <=0;
    }//点在圆内
    P LeftcutPoint(const P &p)const
    {
        P v=p-cent;
        ld sita=acos(r/v.length());
        v=v.rotate({0,0},sita);
        v=v/v.length()*r;
        return cent+v;
    }//左切点
    P RightcutPoint(const P &p)const
    {
        P v=p-cent;
        ld sita=acos(r/v.length());
        v=v.rotate({0,0},-sita);
        v=v/v.length()*r;
        return cent+v;
    }//右切点
    bool isct3(const LINE &L)const
    {
        return sgn(L.dis3from(cent)-r)<=0;
    }//圆与直线相交
    P vecto(const LINE &L)const
    {
        P v=L.p2-L.p1;
        v=v.rotate({0,0},pi/2);
        if (sgn(v%(L.p1-cent))<0) v=v.rotate({0,0},pi);
        return v/v.length()*r;
    }//从圆心垂直射向直线的向量，长度为r
    P LeftisctPoint(const LINE &L)const
    {
        P v=vecto(L);
        ld d=L.dis3from(cent);
        ld sita=acos(d/r);
        return cent+v.rotate({0,0},sita);
    }//左交点
    P RightisctPoint(const LINE &L)const
    {
        P v=vecto(L);
        ld d=L.dis3from(cent);
        ld sita=acos(d/r);
        return cent+v.rotate({0,0},-sita);
    }//右交点
    bool separate(const CIRCLE &C)const
    {
        ld d=(cent-C.cent).length();
        return sgn(r+C.r-d)<=0;
    }//相离
    bool contain(const CIRCLE &C)const
    {
        if (sgn(r-C.r)<0) return 0;
        ld d=(cent-C.cent).length();
        return sgn( d+C.r-r)<=0;
    }//包含
    ld isctarea(const CIRCLE &C)const
    {
        if (separate(C)) return 0;
        if (contain(C)) return C.area();
        if (C.contain(*this)) return area();
        ld d=(cent-C.cent).length();
        ld ang1=acos( (r*r+d*d-C.r*C.r)/2/r/d );
        ld ang2=acos( (C.r*C.r+d*d-r*r)/2/C.r/d);
        return ang1*r*r+ang2*C.r*C.r
               -r*r*sin(2*ang1)/2-C.r*C.r*sin(2*ang2)/2;
    }//圆相交面积，分两个三角形减，否则被codeforces卡精度
};

const int N=100005;
P a[N];
P b[N];
int cnt[N];
int f[N];
lod w,h; 
bool cmp(const P &a,const P &b){
    return a.val<b.val;
}
LINE line[5];
int tp=1;
bool inside(const P &p){
	return sgn(p.x)>=0&&sgn(w-p.x)>=0&&
		   sgn(p.y)>=0&&sgn(h-p.y)>=0;
}
P isct(const LINE &L){
	for (int j=1;j<=4;j++)
		if (line[j].have1(L.p1)){
			if (!line[j].parallel(L)) tp/=0;
			int tmp= sgn( (L.p2-L.p1)%(line[j].p2-line[j].p1));
			if (sgn((L.p2-L.p1).length())==0) tp/=0;
			if (tmp==0) tp/=0;
			if (tmp<0) return L.p1;
			else return L.p2;
		}
	if (sgn(L.length())==0) tp/=0;
    for (int j=1;j<=4;j++){
        if (L.parallel(line[j])) continue;
        if (L.isct21(line[j])) return L.isctPoint(line[j]);
    }
	tp/=0;//???
    return {0,0};
}
int main(){
    int t; scanf("%d",&t);
    while(t--){
        kr(h); kr(w);
        line[1]={{0,h},{0,0}};
        line[2]={{0,0},{w,0}};
        line[3]={{w,0},{w,h}};
        line[4]={{w,h},{0,h}};
        CIRCLE CR; kr(CR.r); CR.cent.read();
        int n; scanf("%d",&n);
        int tot=0;
        for (int i=1;i<=n;i++){
			a[i].read();
			if (!inside(a[i])) tp/=0;
			if (CR.have(a[i])) tp/=0;
		}
        for (int i=1;i<=n;i++){
            P lp=CR.LeftcutPoint(a[i]);
			if (!inside(lp)) tp/=0;
            LINE CUTL={lp,lp*2-a[i]};
            b[++tot]=isct(CUTL);
            b[tot].id=-i;
            b[tot].val=atan2(b[tot].y-h/2,b[tot].x-w/2);
            P rp=CR.RightcutPoint(a[i]);
			if (!inside(rp)) tp/=0;
            LINE CUTR={rp,rp*2-a[i]};
            b[++tot]=isct(CUTR);
            b[tot].id=i;
            b[tot].val=atan2(b[tot].y-h/2,b[tot].x-w/2);
        }
        sort(b+1,b+tot+1,cmp);
        for (int i=tot+1;i<=tot*2;i++) b[i]=b[i-tot];
        int now=0;
        for (int i=1;i<=n;i++) cnt[i]=0;
        for (int i=1;i<=tot*2;i++){
            if (b[i].id<0){
                if (cnt[-b[i].id]) cnt[-b[i].id]--,now--;
            }
            if (b[i].id>0) cnt[b[i].id]++,now++;
            f[i]=now;
        }
        int ans=0;
        for (int i=1;i<=tot*2;i++)
            ans=max(ans,f[i]);
        printf("%d\n",ans);
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 227ms, 内存消耗: 1512K, 提交时间: 2018-07-17 21:33:04 

#include<bits/stdc++.h>
using namespace std;
#define N 10001
#define eps 1e-3
#define ld long double
int T,n,C,cnt,ans;
ld x,y,r,h,w;
struct P{ld x,y;}c;
struct line{P A,B;};
struct rua{ld v;int k;}d[2*N];
ld val(P k)
{
	if(k.x==0)return k.y;
	if(k.y==h)return k.x+h;
	if(k.x==w)return w+2*h-k.y;
	return 2*w+2*h-k.x;
}
bool cmp(rua A,rua B){return A.v<B.v;}
ld dis(P a,P b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
P get(P O,ld dx,ld dy)
{
	ld x,y,k;
	//cout<<dx <<" "<<dy<<endl;
	if(fabs(dx)>eps){
	x=0.0;
	k=(x-O.x)/dx;
	if(k<0)x=w,k=(x-O.x)/dx;
	y=O.y+k*dy;
	if(y<=h && y>=0)
	  return {x,y};
	}
	y=0.0;
	k=(y-O.y)/dy;
	if(k<0)y=h,k=(y-O.y)/dy;
	x=O.x+k*dx;
	return {x,y};
}
double R(P k)
{
	ld x=val(k);
	double res=round(x*1000);
	return res*0.001;
}
void print(P k)
{
	cout<<k.x<<" "<<k.y<<"   ";
}
void init()
{
	C=cnt=0;
	memset(d,0,sizeof(d));
	cin>>h>>w>>r>>c.x>>c.y>>n;
	for(int i=1;i<=n;i++)
	  {
	  cin>>x>>y;
	  ld D=dis(c,{x,y});
	  ld l=sqrt(D*D-r*r);
	  //ld theta=asin(r/dis(c,{x,y}));
	  //ld alpha=atan2(c.x-x,c.y-y);
	  //ld sint=r/dis(c,{x,y});
	  //ld cost=sqrt(1-sint*sint);
	  //ld cosa=(c.x-x)/dis(c,{x,y});
	  //ld sina=sqrt(1-cosa*cosa);
	  //cout<<dis(c,{x,y})<<endl<<theta<<" "<<alpha<<endl;
	  P a=get({x,y},l*(c.x-x)-r*(c.y-y),l*(c.y-y)+r*(c.x-x));
	  P b=get({x,y},l*(c.x-x)+r*(c.y-y),l*(c.y-y)-r*(c.x-x));
	  //print(a);print(b);cout<<endl;
	  //if(val(b)<val(a))swap(a,b);
	  //if(val(b)-val(a)<w+h)cnt++,swap(a,b);
	  //print(a);print(b);cout<<endl;
	  if(val(a)<val(b))cnt++;swap(a,b);
	  d[++C]={val(a),1},d[++C]={val(b),-1};
	  //print({x,y});print(a);print(b);cout<<endl;
	  }
	sort(d+1,d+C+1,cmp);
	ans=cnt;
	for(int i=1;i<=C;i++)
	  {
	  int j=i,add=0,del=0;
	  while(j<=C && d[j].v-d[i].v<eps)
	    {d[j].k<0?del++:add++;j++;}
	  i=j-1;
	  ans=max(ans,cnt+add);
	  cnt+=add-del;
	  }
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)init();
	return 0;
}

上一题

© 2024 nowcoder.com