提出 #372168

---

ソースコード 拡げる

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef long double ld;
typedef complex<ld> P;
typedef vector<P> VP;
const ld eps = 1e-6, pi = acos(-1.0);

ld dot (P a, P b) { return real(conj(a) * b); }
ld cross (P a, P b) { return imag(conj(a) * b); }

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

struct L{ P a, b; };
struct C { P p; ld r; };

int ccw (P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > eps) return 1;   // counter clockwise
  if (cross(b, c) < -eps) return -1; // clockwise
  if (dot(b, c) < 0) return 2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;  // a--b--c on line
  return 0;                          // a--c--b on line
}

P is_ll(L s, L t){
  P sv = s.b - s.a, tv = t.b - t.a;
  return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}

VP ConvexCut(const VP &ps, L l) {
  VP Q;
  for (int i = 0; i < (int)ps.size(); i++) {
    P A = ps[i], B = ps[(i+1)%ps.size()];
    if (ccw(l.a, l.b, A) != -1) Q.push_back(A);
    if (ccw(l.a, l.b, A) * ccw(l.a, l.b, B) < 0)
      Q.push_back(is_ll((L){A, B}, l));
  }
  return Q;
}

void query(VP &polygon, ld angle) {
  cout << "? " << angle << endl;
  ld y; cin >> y;
  ld rad = -angle/180.0*pi;
  P rot = P(cos(rad), sin(rad));
  L l = (L){P(3000, y) * rot, P(-3000, y) * rot};
  polygon = ConvexCut(polygon, l);
}

int main() {
  cout << setprecision(12) << fixed;
  VP polygon;
  polygon.push_back(P( 2000,  2000));
  polygon.push_back(P(-2000,  2000));
  polygon.push_back(P(-2000, -2000));
  polygon.push_back(P( 2000, -2000));
  for (ld angle = 0.85; angle < 400; angle += 8)
    query(polygon, angle);
  VP poly = polygon;
  int n = poly.size();
  REP(i,n) REP(j,n) {
    if (i == j) continue;
    P vec = poly[i] - poly[j];
    query(polygon, -arg(vec) / pi * 180.0);
  }
  int id = -1;
  REP(i,polygon.size()) {
    if (abs(polygon[i] - P(0, 0)) < eps) id = i;
  }
  assert(id >= 0);
  int m = polygon.size();
  assert(m <= 10);
  REP(i,m) {
    P p = polygon[(i+id)%m];
    if (abs(polygon[(i+id+1)%m] - p) < eps) continue;
    if (p.real() < 0) p += P(-eps, 0);
    else p += P(eps, 0);
    if (p.imag() < 0) p += P(0, -eps);
    else p += P(0, eps);
    cout << "! " << (int)(p.real()) << " " << (int)(p.imag()) << endl;
  }
  return 0;
}

提出情報

ジャッジ結果