宝探し (KUPC 2012)

http://kupc2012.contest.atcoder.jp/tasks/kupc2012_9#

問題

略

解法

解説参照。デバック時間は測定忘れた。

// Implement 30min
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const long double EPS = 1e-9;
static const long double PI = acos(-1.0);

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define FOREQ(i, s, n) for (ll i = (s); i <= (ll)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

#include <complex>

typedef complex<long double> Point;
typedef vector<Point> Polygon;
long double INF = 2e+4;

#define CURR(P, i) (P[i])
#define NEXT(P, i) (P[(i + 1) % P.size()])

struct Line : public vector<Point> {
  Line() {;}
  Line(Point a, Point b) { push_back(a); push_back(b); }
};

struct Circle {
  Point p;
  long double r;
  Circle() {;}
  Circle(Point p, long double r) : p(p), r(r) {;}
};

namespace std {
  bool operator<(const Point &lhs, const Point &rhs) {
    return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real();
  }
}

inline long double cross(const Point &a, const Point &b) {
  return imag(conj(a) * b);
}

inline long double dot(const Point &a, const Point &b) {
  return real(conj(a) * b);
}

inline int ccw(Point a, Point b, Point c) {
  b -= a;
  c -= a;
  if (cross(b, c) > 0) { return 1; }
  if (cross(b, c) < 0) { return -1; }
  if (dot(b, c) < 0) { return 2; }
  if (norm(b) < norm(c)) { return -2; }
  return 0;
}

bool intersectSP(const Line &s, const Point &p) {
  return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS;
}

Point crosspointSS(const Line &l, const Line &m) {
  long double A = cross(l[1] - l[0], m[1] - m[0]);
  long double B = cross(l[1] - l[0], l[1] - m[0]);
  if (abs(A) < EPS && abs(B) < EPS) {
    if (intersectSP(l, m[0])) { return m[0]; }
    if (intersectSP(l, m[1])) { return m[1]; }
    if (intersectSP(m, l[0])) { return l[0]; }
    if (intersectSP(m, l[1])) { return l[1]; }
    return m[0];
  }
  if (abs(A) < EPS) { assert(false); }
  return m[0] + B / A * (m[1] - m[0]);
}

Polygon ConvexCut(const Polygon &P, const Line &l) {
  Polygon Q;
  for (int i = 0; i < (int)P.size(); i++) {
    Point A = CURR(P, i), B = NEXT(P, i);
    if (ccw(l[0], l[1], A) != -1) { Q.push_back(A); }
    if (ccw(l[0], l[1], A) * ccw(l[0], l[1], B) < 0) {
      Q.push_back(crosspointSS(Line(A, B), l));
    }
  }
  return Q;
}

//============================================================

Point Gravity(const Polygon &poly) {
  Point p(0.0, 0.0);
  long double w = 0.0;
  REP(i, poly.size()) {
    Point q1 = CURR(poly, i);
    Point q2 = NEXT(poly, i);
    long double v = cross(q1, q2);
    Point p2 = (q1 + q2) / 3.0L;
    p = (p * w + p2 * v) / (v + w);
    w += v;
    if (fabs(w) < EPS) { p = q2; }
  }
  return p;
}

Line DegToLine(Point center, long double deg) {
  long double rad = deg * PI / 180.0;
  Point vect(cos(rad), sin(rad));
  return Line(center - vect * INF, center + vect * INF);
}

//============================================================
const int QUERY_MAX = 200;
int query = 0;
void End(Point p) {
  printf("! %.8Lf %.8Lf\n", p.real(), p.imag());
  //fprintf(stderr, "%.8f %.8f\n", p.real(), p.imag());
  fflush(stdout);
}
long double Query(Point p) {
  if (query == QUERY_MAX) { return -1000.0; }
  printf("? %.8Lf %.8Lf\n", p.real(), p.imag());
  fflush(stdout);
  query++;
  long double ret;
  int v = scanf("%Lf", &ret);
  assert(v == 1);
  return ret;
}

long double w, h, E;
Polygon poly;
int main() {
  int v = scanf("%Lf %Lf %Lf", &w, &h, &E);
  assert(v == 3);
  poly.push_back(Point(-w, -h));
  poly.push_back(Point(w, -h));
  poly.push_back(Point(w, h));
  poly.push_back(Point(-w, h));
  REP(iter, 40) {
    Polygon ppoly = poly;
    Point g = Gravity(poly);
    vector<long double> degs;
    while (true) {
      long double theta = Query(g);
      if (theta == -1000.0) { goto end; }
      if (E < 90) {
        Line l = DegToLine(g, theta - 90.0);
        poly = ConvexCut(poly, l);
        goto next;
      } else {
        degs.push_back(theta);
        degs.push_back(theta + 360);
        degs.push_back(theta - 360);
        sort(degs.begin(), degs.end());
        REP(j, degs.size()) {
          REP(i, j) {
            long double diff = degs[j] - degs[i];
            if (60 <= diff && diff <= 120) {
              //fprintf(stderr, "Poly:%d\n", poly.size());
              //FORIT(it, poly) {
              //  fprintf(stderr, "(%f %f) ", it->real(), it->imag());
              //}
              //fprintf(stderr, "G:%f %f\n", g.real(), g.imag());
              //fprintf(stderr, "%f %f\n", degs[i] + 360, degs[j] + 360);
              Line l1 = DegToLine(g, degs[i] + E - 180);
              Line l2 = DegToLine(g, degs[j] - E);
              poly = ConvexCut(poly, l1);
              poly = ConvexCut(poly, l2);
              goto next;
            }
          }
        }
      }
    }
next:;
    if (poly.size() == 0) { poly = ppoly; }
  }
end:
  End(Gravity(poly));
}