[填坑]Andrew Stankevich’s Contest #7解题报告 » ZOJ2608

ZOJ2608
ZOJ2608.cpp


#include <cmath>
#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

struct Point {
  double x, y;

  Point() { }
  explicit Point(double a): x(cos(a)), y(sin(a)) { }
  Point(double _x, double _y): x(_x), y(_y) { }

  double abs2() const { return x * x + y * y; }
  double abs() const { return hypot(x, y); }
  double arg() const { return atan2(y, x); }

  Point scale(double r) const { return Point(x * r, y * r); }
  Point trunc(double r) const { return scale(r / abs()); }

  Point operator-() const { return Point(-x, -y); }
  Point operator+(const Point& o) const { return Point(x + o.x, y + o.y); }
  Point operator-(const Point& o) const { return Point(x - o.x, y - o.y); }

  double operator*(const Point& o) const { return x * o.x + y * o.y; }
  double operator%(const Point& o) const { return x * o.y - y * o.x; }

  Point project(const Point& o) const {
    return Point(o * *this, o % *this).scale(1.0 / o.abs2());
  }

  Point transform(const Point& o) const {
    return Point(x * o.x - y * o.y, x * o.y + y * o.x);
  }
};

const double EPS = 1e-8;
const double PI = acos(-1.0);

bool intersection(const Point& a, const Point& b, const Point& o, double r,
    Point& p1, Point& p2) {
  Point u = (b - a).trunc(1.0), v = (o - a).project(u);
  if (fabs(v.y) > r + EPS) {
    return false;
  } else {
    double d = (r - v.y) * (r + v.y);
    d = sqrt(d <= 0 ? 0 : d);
    p1 = a + u.scale(v.x - d);
    p2 = a + u.scale(v.x + d);
    return true;
  }
}

bool inside(int n, const Point p[], const Point& o) {
  for (int i = 0; i < n; ++i) {
    if ((p[(i + 1) % n] - p[i]) % (o - p[i]) < -EPS) {
      return false;
    }
  }
  return true;
}

bool inside(int n, const Point p[], int m, const Point q[]) {
  for (int i = 0; i < m; ++i) {
    if (!inside(n, p, q[i])) {
      return false;
    }
  }
  return true;
}

vector<double> gao(int n, const Point p[], const Point& o, double r) {
  vector<double> ret;
  Point p1, p2;
  for (int i = 0; i < n; ++i) {
    if (intersection(p[i], p[(i + 1) % n], o, r, p1, p2)) {
      ret.push_back((p1 - o).arg());
      ret.push_back((p2 - o).arg());
    }
  }
  return ret;
}

double frem(double a, double b) {
  double ret = fmod(a, b);
  while (ret < 0) {
    ret += b;
  }
  return ret;
}

bool solve(const Point& o, const Point& a, double r, Point& ret) {
  double d[2][2] = {
    {1 - r * a.x, r * a.y},
    {-r * a.y, 1 - r * a.x}
  };
  double det = d[0][0] * d[1][1] - d[0][1] * d[1][0];
  if (fabs(det) < EPS) {
    return false;
  } else {
    ret.x = (o.x * d[1][1] - d[0][1] * o.y) / det;
    ret.y = (d[0][0] * o.y - o.x * d[1][0]) / det;
    return true;
  }
}

void plot(int n, const Point p[], const char* style) {
  fprintf(stderr, "draw ");
  for (int i = 0; i < n; ++i) {
    fprintf(stderr, "(%lfu,%lfu)--", p[i].x, p[i].y);
  }
  fprintf(stderr, "cycle %s;\n", style);
  fprintf(stderr, "draw fullcircle scaled 3 shifted (%lfu,%lfu);\n", p[0].x, p[0].y);
}

int main() {
  Point p1[4], p2[4], p3[4], u2, o3, u3, q;
  double s1, s2, s3, w, h;
  vector<double> v;

#ifndef __WATASHI__
  freopen("maps.in", "r", stdin);
  freopen("maps.out", "w", stdout);
#else
  fprintf(stderr, "u=1in;\n\n");
#endif
  scanf("%lf%lf%lf%lf%lf", &s1, &w, &h, &s2, &s3);
  for (int i = 0; i < 4; ++i) {
    scanf("%lf%lf", &p3[i].x, &p3[i].y);
  }
  o3 = p3[0];
  u3 = (p3[1] - p3[0]).trunc(1.0);

  if (!solve(o3, u3, s3 / s1, q) ||
    q.x < -EPS ||
    q.x > w + EPS ||
    q.y < -EPS ||
    q.y > h + EPS) {
    puts("impossible");
    return 0;
  }

  p1[0] = Point(0, 0);
  p1[1] = Point(w, 0);
  p1[2] = Point(w, h);
  p1[3] = Point(0, h);
#ifdef __WATASHI__
  fprintf(stderr, "beginfig(1);\n");
  fprintf(stderr, "pickup pencircle scaled 5;\n");
  fprintf(stderr, "fill fullcircle scaled 25 shifted (%lfu,%lfu) withcolor green;\n", q.x, q.y);
  plot(4, p1, "withcolor red");
  plot(4, p3, "withcolor blue");
  fprintf(stderr, "pickup pencircle scaled 1;\n");
#endif

  v = vector<double>(1, 0);
  for (int i = 0; i < 4; ++i) {
    Point d = p1[i] - q;
    if (d.abs() < EPS) {
      continue;
    }

    vector<double> w1 = gao(4, p1, q, d.abs() * s2 / s1);
    for (int j = 0; j < (int)w1.size(); ++j) {
      v.push_back(frem(w1[j] - d.arg(), 2 * PI));
    }

    vector<double> w3 = gao(4, p1, q, d.abs() * s3 / s2);
    for (int j = 0; j < (int)w3.size(); ++j) {
      v.push_back(frem(u3.arg() - (w3[j] - d.arg()), 2 * PI));
    }
  }

  for (int i = 0; i < (int)v.size(); ++i) {
    u2 = Point(v[i]).scale(s2 / s1);
    for (int j = 0; j < 4; ++j) {
      p2[j] = q + (p1[j] - q).transform(u2);
    }
#ifdef __WATASHI__
    plot(4, p2, "");
#endif
    if (inside(4, p1, 4, p2) && inside(4, p2, 4, p3)) {
      for (int j = 0; j < 4; ++j) {
        printf("%.10lf %.10lf%c", p2[j].x, p2[j].y, j == 3 ? '\n' : ' ');
      }
#ifdef __WATASHI__
      plot(4, p2, "withcolor (1,0,1)");
      fprintf(stderr, "endfig;\n\n");
#endif
      return 0;
    }
  }
#ifdef __WATASHI__
  fprintf(stderr, "endfig;\n\n");
  fprintf(stderr, "end\n");
#endif
  puts("impossible");
  return 0;
}
Leave a Reply