Inheritance

题目描述

The old King decided to divide the Kingdom into parts among his three sons. Each part is a polygonal area. Taking into account the bad temper of the middle son the King gave him a part of Kingdom such that moving straight from any place of this part to any other place of this part he will not cross the boundary.
There are several mineral deposits in the Kingdom. Each mineral deposit looks like a straight line segment. The middle son wants to know what part of mineral deposits is located inside his territory (not including the boundaries).

题意概述

给定一个凸$N$边形,求一条线段在它内部的长度(不包括边界)。
数据范围:$3 \le N \le 400$。

算法分析

由于点的顺序是随机的,因此需要先求凸包,接着计算线段与凸包的交点,根据交点个数来分类讨论。
此题细节很多,需要考虑线段与某条边共线、线段顶点在某条边上、线段经过某个顶点等情况。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

static const double EPS = 1e-6;
int cmp(double a, double b) { return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1; }

struct Point {
  double x, y;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {};
  bool operator < (const Point &p) const { return ! cmp(x, p.x) ? cmp(y, p.y) == -1 : cmp(x, p.x) == -1; }
  Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
  Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
  Point operator * (const double &a) const { return Point(x * a, y * a); }
  Point operator / (const double &a) const { return Point(x / a, y / a); }
  double operator * (const Point &p) const { return x * p.y - y * p.x; }
  double operator ! () const { return sqrt(x * x + y * y); }
};

struct Line {
  Point a, b;
  Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
  bool operator | (const Line &l) const { return ! cmp((b - a) * (l.b - l.a), 0); }
  Point operator & (const Line &l) const {
    double t = (a - l.a) * (l.a - l.b) / ((a - b) * (l.a - l.b));
    return a + (b - a) * t;
  }
};

struct Solver {
private:
  static const int N = 410;
  int n, q, top;
  Point point[N], sta[N];
  vector <Point> poly;
  void input() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
    scanf("%d", &q);
  }
  void init() {
    sort(point + 1, point + n + 1);
    for (int i = 1; i <= n; ++ i) {
      while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
      sta[++ top] = point[i];
    }
    for (int i = 1; i <= top; ++ i) poly.push_back(sta[i]); top = 0;
    for (int i = n; i; -- i){
      while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
      sta[++ top] = point[i];
    }
    for (int i = 2; i < top; ++ i) poly.push_back(sta[i]);
  }
  bool in(Point p) {
    for (int i = 0; i < poly.size(); ++ i)
      if (cmp((poly[(i + 1) % poly.size()] - poly[i]) * (p - poly[i]), 0) < 0) return false;
    return true;
  }
  void process() {
    Line l;
    scanf("%lf%lf%lf%lf", &l.a.x, &l.a.y, &l.b.x, &l.b.y);
    for (int i = 0; i < poly.size(); ++ i) {
      Line tmp(poly[i], poly[(i + 1) % poly.size()]);
      if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
        printf("0.00\n"); return;
      }
    }
    vector <Point> inter;
    for (int i = 0; i < poly.size(); ++ i)
      if (! (Line(poly[i], poly[(i + 1) % poly.size()]) | l)) {
        Line tmp = Line(poly[i], poly[(i + 1) % poly.size()]);
        Point p = tmp & l;
        if ((cmp(p.x, l.a.x) || cmp(p.y, l.a.y)) && (cmp(p.x, l.b.x) || cmp(p.y, l.b.y)) && cmp(min(l.a.x, l.b.x), p.x) < 1 && cmp(p.x, max(l.a.x, l.b.x)) < 1 && cmp(min(l.a.y, l.b.y), p.y) < 1 && cmp(p.y, max(l.a.y, l.b.y)) < 1 && cmp(min(tmp.a.x, tmp.b.x), p.x) < 1 && cmp(p.x, max(tmp.a.x, tmp.b.x)) < 1 && cmp(min(tmp.a.y, tmp.b.y), p.y) < 1 && cmp(p.y, max(tmp.a.y, tmp.b.y)) < 1) {
          for (int j = 0; j < inter.size(); ++ j) if (! cmp(inter[j].x, p.x) && ! cmp(inter[j].y, p.y)) goto label;
          inter.push_back(p);
        }
        label: ;
      }
    for (int i = 0; i < poly.size(); ++ i) {
      Line tmp(poly[i], poly[(i + 1) % poly.size()]);
      if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
        printf("0.00\n"); return;
      }
    }
    if (inter.empty())
      if (in(l.a) && in(l.b)) printf("%.2lf\n", ! (l.b - l.a));
      else printf("0.00\n");
    else if (inter.size() == 2) printf("%.2lf\n", ! (inter[1] - inter[0]));
    else if (in(l.a)) printf("%.2lf\n", ! (inter[0] - l.a));
    else if (in(l.b)) printf("%.2lf\n", ! (inter[0] - l.b));
    else printf("0.00\n");
  }

public:
  void solve() { input(), init(); while (q --) process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *