HDU-3644 A Chocolate Manufacturer's Problem 计算几何 模拟退火

HDU-3644 A Chocolate Manufacturer’s Problem

题意: 给定一个多边形, 判断这个多边形中是否可以放入一个半径为r的圆.
分析: 发现不知从何入手时就开始模拟退火吧. 随机找出圆心坐标, 主要就是判断某个点是否在多边形内. 这题wa和tle了好多次, 参数选择需要些微调, 模拟退火有风险, 罚时伤不起.
代码:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>using namespace std;const int MAXN = 111;
const double pi = acos(-1);
const double inf = 0x3f3f3f3f;
const double eps = 1e-4;int sgn(double x) {
    if (fabs(x) < eps)return 0;else if (x < 0)return -1;elsereturn 1;
}struct Point {
    double x, y;Point() {
    }Point(double _x, double _y) {
    x = _x;y = _y;}Point operator+(const Point b) const {
     return Point(x + b.x, y + b.y); }Point operator-(const Point b) const {
     return Point(x - b.x, y - b.y); }double operator*(const Point b) const {
     return x * b.x + y * b.y; }double operator^(const Point b) const {
     return x * b.y - y * b.x; }bool operator==(const Point b) {
    return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;}double distance(Point b) {
     return hypot(x - b.x, y - b.y); }
};struct Line {
    Point s, e;Line() {
    }Line(Point _s, Point _e) {
    s = _s;e = _e;}double length() {
     return s.distance(e); }double dispointtoline(Point b) {
     return fabs((b - s) ^ (e - s)) / length(); }double dispointtoseg(Point b) {
    if (sgn((b - s) * (e - s)) < 0 || sgn((b - e) * (s - e)) < 0)return min(b.distance(s), b.distance(e));elsereturn dispointtoline(b);}bool pointonseg(Point b) {
    return sgn((b - s) ^ (e - s)) == 0 && sgn((b - s) * (b - e)) <= 0;}
};struct Polygon {
    Point p[MAXN];Line l[MAXN];int n;void add(Point b) {
     p[n++] = b; }void getline() {
    for (int i = 0; i < n; i++) {
    l[i] = Line(p[i], p[(i + 1) % n]);}}int relationpoint(Point q) {
    for (int i = 0; i < n; i++) {
    if (p[i] == q)return 3;}getline();for (int i = 0; i < n; i++) {
    if (l[i].pointonseg(q))return 2;}int cnt = 0;for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;int k = sgn((q - p[i]) ^ (p[i] - p[j]));int u = sgn(p[i].y - q.y);int v = sgn(p[j].y - q.y);if (k > 0 && u < 0 && v >= 0)cnt++;if (k < 0 && v < 0 && u >= 0)cnt--;}return cnt != 0;}double getdis(Point cir) {
    double res = inf;getline();for (int i = 0; i < n; i++) {
    res = min(res, l[i].dispointtoseg(cir));}// cout << res << endl;return res;}
};Polygon pol;
int n;
double r;
Point ans[MAXN];double Rand() {
     return (double)rand() / RAND_MAX; }
int main() {
    srand(time(NULL));while (scanf("%d", &n) != EOF) {
    if (n == 0)break;pol.n = 0;for (int i = 0; i < n; i++) {
    double x, y;scanf("%lf%lf", &x, &y);pol.add(Point(x, y));}scanf("%lf", &r);double x1 = pol.p[0].x, x2 = pol.p[0].x, y1 = pol.p[0].y, y2 = pol.p[0].y;for (int i = 0; i < n; i++) {
    ans[i].x = (pol.p[i].x + pol.p[(i + 1) % n].x) / 2.0;ans[i].y = (pol.p[i].y + pol.p[(i + 1) % n].y) / 2.0;x1 = min(x1, pol.p[i].x);x2 = max(x2, pol.p[i].x);y1 = min(y1, pol.p[i].y);y2 = max(y2, pol.p[i].y);}double res = -inf;double T = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)) / 2;// cout << " --------------- " << endl;bool flag = 0;while (T > eps && !flag) {
    for (int j = 0; j < n; j++) {
    for (int i = 0; i < 5; i++) {
    Point nxt;nxt.x = ans[j].x + T * (Rand() * 2 - 1);nxt.y = ans[j].y + T * (Rand() * 2 - 1);if (pol.relationpoint(nxt) != 1)continue;// cout << nxt.x << " " << nxt.y << endl;double dis = pol.getdis(nxt);if (sgn(res - dis) < 0) {
    res = dis;ans[j] = nxt;if (sgn(res - r) >= 0)flag = 1;}}}T *= 0.9;}// cout << res << endl;printf("%s\n", !flag ? "No" : "Yes");}return 0;
}