BZOJ 2823 AHOI 2012 ÐźÅËþ ͹°ü+×îСԲ¸²¸Ç
ÌâÄ¿´óÒ⣺¸ø³öƽÃæÉÏn¸öµã£¬Çó×îСԲ¸²¸Ç¡£
˼·£ºÔ²¸²¸ÇÎÊÌâÖ»ÓëËùÓеãÖÐ͹°üÉϵĵãÓйأ¬Òò´ËÏÈÇóÒ»ÏÂ͹°ü£¬È»ºóÊý¾Ý·¶Î§Öè¼õ¡£´ó¸ÅÊÇֻʣÏÂlogn×óÓÒ¸öµã¡£ÕâÑù¾Í¿ÉÒÔËæ±ãÀËÁË¡£
ÏÈÕÒËùÓÐÈý¸öµã×é³ÉµÄÔ²£¬È»ºóÕÒÁ½¸öµãΪֱ¾¶Ëù×é³ÉµÄÔ²¡£
»¹ÓоÍÊÇÈý½ÇÐεÄÍâÐĹ«Ê½£¬¼òÖ±²»ÊÇÈËÍƵģ¬È»ºóÎҾͻúÖƵİٶÈÁË£¬½á¹ûÈçÏ£º
²»ÒªÄ£ÄâÍ˻𡣡£¡£<†·Ÿ"http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+0fnA/brcv9OjrLWxxOPL47P2Mi40OSAyLjg2tcTKsbryo6yyu9KqyM/OqsTjsbu/qL6rwcujrMbkyrXKx8Tj0LS50sHLoaOho6GjPC9wPgo8cD48YnI+CjwvcD4KPHA+Q09ERaO6PGJyPgo8YnI+CjxwcmUgY2xhc3M9"brush:java;">#include
#include
#include
#include
#include
#include
#define MAX 1000010
#define INF 1e15
using namespace std;
#define sqr(a) ((a) * (a))
struct Point{
double x,y,alpha;
Point(double _,double __):x(_),y(__) {}
Point() {}
bool operator <(const Point &a)const {
return alpha < a.alpha;
}
Point operator -(const Point &a)const {
return Point(x - a.x,y - a.y);
}
void Read() {
scanf("%lf%lf",&x,&y);
}
void Calc(const Point &p) {
alpha = atan2(y - p.y,x - p.x);
}
}point[MAX];
int cnt;
double min_x = INF,min_y = INF;
Point stack[MAX];
int top;
double Cross(const Point &p,const Point &q)
{
return p.x * q.y - p.y * q.x;
}
double Calc(const Point &a,const Point &b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double CalcX(const Point &p1,const Point &p2,const Point &p3)
{
double up = sqr(p1.x) * (p2.y - p3.y) + sqr(p2.x) * (p3.y - p1.y) + sqr(p3.x) * (p1.y - p2.y);
up -= (p1.y - p2.y) * (p2.y - p3.y) * (p3.y - p1.y);
double down = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
return up / (2 * down);
}
double CalcY(const Point &p1,const Point &p2,const Point &p3)
{
double up = -(sqr(p1.y) * (p2.x - p3.x) + sqr(p2.y) * (p3.x - p1.x) + sqr(p3.y) * (p1.x - p2.x));
up += (p1.x - p2.x) * (p2.x - p3.x) * (p3.x - p1.x);
double down = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
return up / (2 * down);
}
inline double Judge(double x,double y)
{
double re = .0;
for(int i = 0; i <= top; ++i)
re = max(re,Calc(Point(x,y),stack[i]));
return re;
}
int main()
{
cin >> cnt;
for(int i = 1; i <= cnt; ++i)
point[i].Read();
int p;
for(int i = 1; i <= cnt; ++i)
if(point[i].y < min_y) {
min_y = point[i].y;
min_x = point[i].x;
p = i;
}
else if(point[i].y == min_y && point[i].x < min_x) {
min_x = point[i].x;
p = i;
}
for(int i = 1; i <= cnt; ++i)
if(i != p)
point[i].Calc(point[p]);
sort(point + 1,point + cnt + 1);
stack[top] = point[1];
stack[++top] = point[2];
stack[++top] = point[3];
for(int i = 4; i <= cnt; ++i) {
while(top >= 2 && Cross(stack[top] - stack[top - 1],point[i] - stack[top - 1]) <= 0)
--top;
stack[++top] = point[i];
}
double ans = INF;
double X,Y,x,y,r;
for(int i = 0; i <= top; ++i)
for(int j = i + 1; j <= top; ++j)
for(int k = j + 1; k <= top; ++k) {
x = CalcX(stack[i],stack[j],stack[k]);
y = CalcY(stack[i],stack[j],stack[k]);
r = Judge(x,y);
if(r < ans) {
ans = r;
X = x,Y = y;
}
}
for(int i = 0; i <= top; ++i)
for(int j = 0; j <= top; ++j) {
r = Judge((stack[i].x + stack[j].x) / 2,(stack[i].y + stack[j].y) / 2);
if(r < ans) {
ans = r;
X = (stack[i].x + stack[j].x) / 2;
Y = (stack[i].y + stack[j].y) / 2;
}
}
printf("%.2lf %.2lf %.2lf\n",X,Y,ans);
return 0;
}
