poj3384 Feng Shui

发表于 | 更新于

Link

Solution

要让两个圆覆盖的面积最大，而且不能与边相交。 于是，将凸包上的边内移半径长度，然后求半平面交，得到的区域就是圆心可以存在的区域。 贪心地选择两个最远的点。（在边上肯定不如在点上远？），旋转卡壳。 旋转卡壳比O(n2)O(n^2)枚举慢？？常数大？ 貌似，求单位法向量， 内移求内核是个常见的套路。

Tips:多边形的内核

它是平面简单多边形的核是该多边形内部的一个点集，该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。就是一个在一个房子里面放一个摄像头，能将所有的地方监视到的放摄像头的地点的集合即为多边形的核。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//Code by Lucida
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100+1;
using std::reverse;
using std::pair;
using std::sort;
using std::make_pair;
typedef double ld;
const ld eps=1e-7,pi=acos(-1.0);
int fcmp(ld x)
{
    if(-eps<x && x<eps) return 0;
    return x<0?-1:1;
}
template <class T> T sqr(T x){return x*x;}
template <class T> T abs(T x){return x>0?x:-x;}
struct vec
{
    ld x,y;
    vec(ld _x=0,ld _y=0):x(_x),y(_y){}
    vec operator -(){return vec(-x,-y);}
    ld norm(){return sqrt(x*x+y*y);}
    bool operator <(vec a)
    {
        if(x!=a.x) return x<a.x;
        return y<a.y;
    }
    void operator +=(vec a){x+=a.x,y+=a.y;}
    void operator -=(vec a){x-=a.x,y-=a.y;}
    void operator /=(ld a){x/=a,y/=a;}
    void operator *=(ld a){x*=a,y*=a;}
    bool operator ==(vec a){return x==a.x && y==a.y;}
	vec normal();
};
typedef vec point;
vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
vec operator *(vec a,ld t){return vec(a.x*t,a.y*t);}
vec operator /(vec a,ld t){return vec(a.x/t,a.y/t);}
ld inner(vec a,vec b){return a.x*b.x+a.y*b.y;}
ld outer(vec a,vec b){return a.x*b.y-a.y*b.x;}
vec rotate(vec a,ld rad){return vec(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
vec vec::normal()
{
	vec nm=rotate(*this,pi/2);
	nm/=nm.norm();
	return nm;
}
struct line
{
	point a;vec v;ld angle;
	line(){}
	line(point _a,vec _v):a(_a),v(_v){angle=atan2(v.y,v.x);}
	bool operator <(const line &a)const{return angle<a.angle;}
};
bool parl(line a,line b){return fcmp(outer(a.v,b.v))==0;}
bool onleft(point a,line b){return fcmp(outer(b.v,a-b.a))>=0;}//>=?
point cross(line a,line b){return a.a+a.v*outer(a.a-b.a,b.v)/outer(b.v,a.v);}
int intersect(line *l,int n,point *tio)
{
	sort(l+1,l+1+n);
	static point Qp[MAXN];
	static line Ql[MAXN];
	int head,tail;
	Ql[head=tail=1]=l[1];
	#define count(x,y) (y-x+1)
	for(int i=2;i<=n;i++)
	{
		while(count(head,tail)>=2 && !onleft(Qp[tail-1],l[i])) tail--;
		while(count(head,tail)>=2 && !onleft(Qp[head],l[i])) head++;
		Ql[++tail]=l[i];
		if(parl(Ql[tail-1],Ql[tail]))
		{
			tail--;
			if(onleft(l[i].a,Ql[tail])) Ql[tail]=l[i];
		}
		if(count(head,tail)>=2) Qp[tail-1]=cross(Ql[tail-1],Ql[tail]);
	}
	while(count(head,tail)>=2 && !onleft(Qp[tail-1],Ql[head])) tail--;
	Qp[tail]=cross(Ql[head],Ql[tail]);
	for(int i=head;i<=tail;i++) *++tio=Qp[i]; 
	return count(head,tail);
	#undef count
}
ld dist(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
ld dist(point a,line l){return abs(outer(a-l.a,l.v))/l.v.norm();}
pair<point,point> caliper(point *p,int n)
{
	pair<point,point> pa;
	ld ANS=-1;
	#define suc(i) (i+1>n?1:i+1)
	for(int i=1,cur=2;i<=n;i++)
	{
		line now=line(p[i],p[suc(i)]-p[i]);
		while(fcmp(dist(p[cur],now)-dist(p[suc(cur)],now))<0) cur=suc(cur);
		if(chkmx(ANS,dist(p[cur],p[i]))) pa=make_pair(p[cur],p[i]);
		if(chkmx(ANS,dist(p[cur],p[suc(i)]))) pa=make_pair(p[cur],p[suc(i)]);
	}
	return pa;
	#undef suc
	/*
	pair<point,point> pa;
	ld res=-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(chkmx(res,dist(p[i],p[j])))
				pa=make_pair(p[i],p[j]);
	return pa;*/
}
int main()
{
	freopen("input","r",stdin);
	static point p[MAXN];
	static line l[MAXN];
	int n;red(n);
	ld r;fred(r);
	for(int i=1;i<=n;i++) fred(p[i].x),fred(p[i].y);
	reverse(p+1,p+1+n);
	for(int i=1;i<=n;i++) l[i]=line(p[i],vec(p[i+1>n?1:i+1]-p[i]));
	for(int i=1;i<=n;i++) l[i].a+=l[i].v.normal()*r;
	n=intersect(l,n,p);
	pair<point,point> ANS=caliper(p,n);
	printf("%.4f %.4f %.4f %.4f",ANS.first.x,ANS.first.y,ANS.second.x,ANS.second.y);
	return 0;
}