3384 -- Feng Shui

  构造半平面交,然后求凸包上最远点对。

  这题的题意是给出一个凸多边形区域,要求在其中放置两个半径为r的圆(不能超出凸多边形区域),要求求出两个圆心,使得多边形中没有被覆盖的面积最小。反之就是求圆覆盖的区域最大。首先我们可以求出圆心放置的位置的区域,这个要利用半平面交,将原多边形区域向内收缩r的距离。要求两个圆覆盖的区域最大,也就是它们相交的面积最小,也就是两个圆心的距离要尽可能的大。这样就说明了,这题的做法是要求出凸包上面的最远点对。

  做这题的时候犯了两个错误,一个是没有设置对精度,直接用了cout的默认输出,另一个则是没有想到收缩以后,剩余的多边形的顶点数会少于n。

代码如下:

 #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath> using namespace std; struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
} ;
template<class T> T sqr(T x) { return x * x;} typedef Point Vec;
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, double p) { return Vec(a.x * p, a.y * p);}
Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);} const double EPS = 1e-;
const double PI = acos(-1.0);
inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
bool operator < (Point a, Point b) { return sgn(a.x - b.x) < || sgn(a.x - b.x) == && a.y < b.y;}
bool operator == (Point a, Point b) { return sgn(a.x - b.x) == || sgn(a.y - b.y) == ;} inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
inline double dotDet(Point o, Point a, Point b) { return dotDet(a - o, b - o);}
inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
inline double toRad(double deg) { return deg/ 180.0 * PI;}
inline double angle(Vec v) { return atan2(v.y, v.x);}
Vec normal(Vec x) {
double len = vecLen(x);
return Vec(-x.y, x.x) / len;
} struct Poly {
vector<Point> pt;
Poly() { pt.clear();}
~Poly() {}
Poly(vector<Point> &pt) : pt(pt) {}
Point operator [] (int x) const { return pt[x];}
int size() { return pt.size();}
double area() {
double ret = 0.0;
int sz = pt.size();
for (int i = ; i < sz; i++) {
ret += crossDet(pt[i], pt[i - ]);
}
return fabs(ret / 2.0);
}
} ; struct DLine {
Point p;
Vec v;
double ang;
DLine() {}
DLine(Point p, Vec v) : p(p), v(v) { ang = atan2(v.y, v.x);}
bool operator < (const DLine &L) const { return ang < L.ang;}
DLine move(double x) {
Vec nor = normal(v);
nor = nor * x;
return DLine(p + nor, v);
}
} ; inline bool onLeft(DLine L, Point p) { return crossDet(L.v, p - L.p) > ;}
Point dLineIntersect(DLine a, DLine b) {
Vec u = a.p - b.p;
double t = crossDet(b.v, u) / crossDet(a.v, b.v);
return a.p + a.v * t;
} Poly halfPlane(DLine *L, int n) {
Poly ret = Poly();
sort(L, L + n);
int fi, la;
Point *p = new Point[n];
DLine *q = new DLine[n];
q[fi = la = ] = L[];
for (int i = ; i < n; i++) {
while (fi < la && !onLeft(L[i], p[la - ])) la--;
while (fi < la && !onLeft(L[i], p[fi])) fi++;
q[++la] = L[i];
if (fabs(crossDet(q[la].v, q[la - ].v)) < EPS) {
la--;
if (onLeft(q[la], L[i].p)) q[la] = L[i];
}
if (fi < la) p[la - ] = dLineIntersect(q[la - ], q[la]);
}
while (fi < la && !onLeft(q[fi], p[la - ])) la--;
if (la < fi) return ret;
p[la] = dLineIntersect(q[la], q[fi]);
for (int i = fi; i <= la; i++) ret.pt.push_back(p[i]);
return ret;
} const int N = ;
Point pt[N];
DLine dl[N]; int main() {
// freopen("in", "r", stdin);
int n;
double r;
while (cin >> n >> r) {
for (int i = ; i < n; i++) {
cin >> pt[i].x >> pt[i].y;
if (i) dl[i - ] = DLine(pt[i], pt[i - ] - pt[i]).move(r + EPS);
}
dl[n - ] = DLine(pt[], pt[n - ] - pt[]).move(r + EPS);
Poly tmp = halfPlane(dl, n);
if (tmp.size() <= ) {
for (int i = ; i < n; i++) {
if (i) dl[i - ] = DLine(pt[i], pt[i - ] - pt[i]).move(r - EPS);
}
dl[n - ] = DLine(pt[], pt[n - ] - pt[]).move(r - EPS);
tmp = halfPlane(dl, n);
}
double dis = 0.0;
int id[] = { , };
n = tmp.size();
for (int i = ; i < n; i++) {
for (int j = ; j < n; j++) {
if (dis < vecLen(tmp[i] - tmp[j])) {
dis = vecLen(tmp[i] - tmp[j]);
id[] = i;
id[] = j;
}
}
}
// cout << vecLen(tmp[id[0]] - tmp[id[1]]) << endl;
cout.precision();
cout << tmp[id[]].x << ' ' << tmp[id[]].y << ' ' << tmp[id[]].x << ' ' << tmp[id[]].y << endl;
}
return ;
}

  吸取教训,继续努力!

——written by Lyon

最新文章

  1. mysql基于“时间”的盲注
  2. PostGr-SQL 基本概念
  3. poj 1691 图方块 end
  4. 集成Jenkins Notifier for Chrome到Jenkins CI
  5. 2016/7/6 神&#183;CPU的人类极限在哪?
  6. 【贪心+堆】XMU 1584 小明的烦恼
  7. 《Two Days DIV + CSS》读书笔记——CSS控制页面方式
  8. 网易云课堂_C语言程序设计进阶_第6周:程序结构
  9. HDU 4893 Wow! Such Sequence!(2014年多校联合 第三场 G)(线段树)
  10. Codeforces 39E What Has Dirichlet Got to Do with That? 游戏+内存搜索
  11. Archaius 原理
  12. JS数组添加删除
  13. python复习基本知识
  14. 【Teradata SQL】十进制转换成二进制
  15. 不会点git真不行啊.
  16. How to identify safari in Mac?
  17. 20155201 网络攻防技术 实验八 Web基础
  18. Android 开源项目 eoe 社区 Android 客户端
  19. Struts2拦截器的配置
  20. 面试题46:求1+2+ …… +n

热门文章

  1. 杨柳絮-Info:春天将不再漫天飞“雪”,济源治理杨柳絮在行动
  2. Ubuntu的网络共享
  3. DIV+CSS网页布局常用的一些基础知识整理
  4. Python学习笔记(三)字符串类型及其操作(2)
  5. SVN经常使用操作
  6. Location 位置 history
  7. B站直播 DEMO ijkplayerDemo
  8. 【心有猛虎】react-lesson
  9. UE4 Pak 相关知识总结
  10. Gatling初次体验