Submission #434979

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

typedef double R;
typedef complex<R> P;

const R EPS = 1e-6;
const R PI = acos((R)(-1));

/*
 -1 -> neg
  0 -> near 0
  1 -> pos
  */
int sgn(R a) {
    if (a < -EPS) return -1;
    if (a > EPS) return 1;
    return 0;
}

/*
 -1 -> a > b
  0 -> a near b
  1 -> a < b
 */
int sgn(R a, R b) {
    return sgn(b-a);
}

bool near(const P &a, const P &b) {
    return !sgn(abs(a-b));
}

/*
 ちょっとロバストな比較関数
 */
bool lessP(const P &l, const P &r) {
    if (sgn(l.real(), r.real())) return l.real() < r.real();
    if (sgn(l.imag(), r.imag())) return l.imag() < r.imag();
    return false;
}

R cross(P a, P b) { return a.real()*b.imag() - a.imag()*b.real(); }
R dot(P a, P b) { return a.real()*b.real() + a.imag()*b.imag(); }

/* 1->cclock
  -1->clock
   0->on
   2->back
  -2->front
  */
int ccw(P a, P b, P c) {
    assert(!near(a, b));
    if (near(a, c) || near(b, c)) return 0;
    int s = sgn(cross(b-a, c-a));
    if (s) return s;
    if (dot(b-a, c-a) < 0) return 2;
    if (dot(a-b, c-b) < 0) return -2;
    return 0;
}

R ssqrt(R d) {
    d = max<R>(0, d);
    return sqrt(d);
}

R sacos(R d) {
    d = max<R>(-1, d);
    d = min<R>(1, d);
    return acos(d);
}

struct L {
    P x, y;
    L() {}
    L(P x, P y) :x(x), y(y) {}
};

P vec(const L &l) {
    return l.y - l.x;
}

R abs(const L &l) {
    return abs(vec(l));
}

R arg(const L &l) {
    return arg(vec(l));
}

//度をラジアンに
R deg2rad(R x) {
    return x/180*PI;
}

//ラジアンを度に
R rad2deg(R x) {
    return x/PI*180;
}

//角度を[0, 2*PI)に
R radNorP(R x) {
    return fmod(fmod(x, 2*PI) + 2*PI, 2*PI);
}

//角度を[-PI, PI)に
R radNorN(R x) {
    x = radNorP(x);
    if (x >= PI) x -= 2*PI;
    return x;
}

/**
 * radianで、xが[l, r]に入っているかを判別する
 * 0:OFF
 * 1:IN
 * 2:ON
 */
bool inR(R l, R r, R x) {
    l = radNorP(l);
    r = radNorP(r);
    x = radNorP(x);
    if (!sgn(l, x) || !sgn(r, x)) return 2;
    if (!sgn(l, r)) return 0;
    if (sgn(l, r) == 1) {
        if (sgn(l, x) == 1 && sgn(x, r) == 1) return 1;
    } else {
        if (sgn(x, r) == 1 || sgn(l, x) == 1) return 1;
    }
    return 0;
}


bool insLS(const L &l, const L &s) {
    int a = ccw(l.x, l.y, s.x);
    int b = ccw(l.x, l.y, s.y);
    if (a == 1 && b == 1) return false;
    if (a == -1 && b == -1) return false;
    return true;
}

bool insSS(const L &s, const L &t) {
    int a = ccw(s.x,s.y,t.x), b = ccw(s.x,s.y,t.y);
    int c = ccw(t.x,t.y,s.x), d = ccw(t.x,t.y,s.y);
    if (a*b <= 0 && c*d <= 0) return true;
    return false;
}

int crossLL(const L &l, const L &m, P &r) {
    L mm = L(m.x - l.x, m.y - l.x);
    mm.x *= polar<R>(1.0, -arg(l));
    mm.y *= polar<R>(1.0, -arg(l));
    if (sgn(vec(mm).imag()) == 0) {
        r = l.x;
        if (sgn(mm.x.imag()) == 0) return -1;
        return 0;
    }
    r = mm.x - vec(mm) * (mm.x.imag() / vec(mm).imag());
    r *= polar<R>(1.0, arg(l));
    r += l.x;
    return 1;
}

int crossSS(const L &l, const L &m, P &r) {
    int u = crossLL(l, m, r);
    if (u == 0) return 0;
    if (u == -1) {
        int x = ccw(l.x, l.y, m.x);
        int y = ccw(l.x, l.y, m.y);
        if (x == 0) {
            r = m.x;
            return -1;
        }
        if (y == 0) {
            r = m.y;
            return -1;
        }
        if (x == y) return 0;
        r = l.x;
        return -1;
    }
    if (ccw(l.x, l.y, r) == 0 && ccw(m.x, m.y, r) == 0) return 1;
    return 0;
}

R distLP(const L &l, const P &p) {
    return abs(cross(vec(l), p-l.x)/abs(vec(l)));
}


//線分と点の最小距離
R distSP(const L &s, const P &p) {
    P s2 = vec(s)*P(0, 1);
    if (ccw(s.x, s.x+s2, p) == 1) return abs(s.x-p);
    if (ccw(s.y, s.y+s2, p) == -1) return abs(s.y-p);
    return min(min(abs(s.x-p), abs(s.y-p)), distLP(s, p));
}

//線分と線分の最小距離
R distSS(const L &s, const L &t) {
    if (insSS(s, t)) return 0;
    return min(min(distSP(s, t.x), distSP(s, t.y)),
               min(distSP(t, s.x), distSP(t, s.y)));
}

//線分アレンジメント
//l->線分 n->線分の数 p->点集合結果 g->エッジの情報
//pのサイズはlC2+2*l確保
//返り値として点集合の個数を返す
int arrange(L l[], int n, P p[], vector<int> g[]) {
    int pc = 0;
    for (int i = 0; i < n; i++) {
        p[pc] = l[i].x; pc++;
        p[pc] = l[i].y; pc++;
        for (int j = i+1; j < n; j++) {
            int u = crossSS(l[i], l[j], p[pc]);
            if (u == 0) continue;
            pc++;
        }
    }
    sort(p, p+pc, lessP);
    pc = unique(p, p+pc, near) - p;
    for (int i = 0; i < n; i++) {
        vector<int> v;
        for (int j = 0; j < pc; j++) {
            if (ccw(l[i].x, l[i].y, p[j]) != 0) continue;
            v.push_back(j);
        }
        sort(v.begin(), v.end(), [&](const int &x, const int &y) 
            {return abs(p[x] - l[i].x) < abs(p[y] - l[i].x);});
        for (int j = 0; j < (int)v.size() - 1; j++) {
            g[v[j]].push_back(v[j+1]);
            g[v[j+1]].push_back(v[j]);
        }
    }

    for (int i = 0; i < pc; i++) {
        sort(g[i].begin(), g[i].end());
        g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
    }
    return pc;
}

struct T {
    P d[3];
    T() {}
    T(P x, P y, P z) {
        d[0] = x; d[1] = y; d[2] = z;
    }
    P& operator[](int p) {
        return d[p];
    }
    const P& operator[](int p) const {
        return d[p];
    }
    int size() const {
        return 3;
    }
};

P cu(const T &t, int i) {
    return t[(i%3+3)%3];
}

typedef vector<P> Pol;

P cu(const Pol &p, int i) { 
    int s = p.size();
    return p[(i%s+s)%s];
};


//0:P is out 1:P is on line 2:P is in
int contains(const T &pol, P p) {
    int in = -1;
    for (int i = 0; i < (int)pol.size(); i++) {
        P a=cu(pol,i)-p, b=cu(pol,i+1)-p;
        if (ccw(a, b, P(0, 0)) == 0) return 1;
        if (imag(a) > imag(b)) swap(a, b);
        if (imag(a) <= 0 && 0 < imag(b)) {
            if (cross(a, b) < 0) in *= -1;
        }
    }
    return in+1;
}

//0:P is out 1:P is on line 2:P is in
int contains(const Pol &pol, P p) {
    int in = -1;
    for (int i = 0; i < (int)pol.size(); i++) {
        P a=cu(pol,i)-p, b=cu(pol,i+1)-p;
        if (ccw(a, b, P(0, 0)) == 0) return 1;
        if (imag(a) > imag(b)) swap(a, b);
        if (imag(a) <= 0 && 0 < imag(b)) {
            if (cross(a, b) < 0) in *= -1;
        }
    }
    return in+1;
}

R area_naive(const Pol &p) {
    R u = 0;
    for (int i = 0; i < (int)p.size(); i++) {
        u += cross(cu(p, i), cu(p, i+1));
    }
    return u/2;
}

R area(const Pol &p) {
    return abs(area_naive(p));
}

/*
 -1 -> clock
 0 -> non polygon
 1 -> counter clock
 */
int iscclock(const Pol &p) {
    return sgn(area_naive(p));
}


/*
 スパゲッティソースをパクった、直線の左側の多角形を返却する   
 */
Pol convex_cut(const Pol &p, const L &l) {
    Pol q;
    for (int i = 0; i < (int)p.size(); i++) {
        P a = cu(p, i), b = cu(p, i+1);
        if (ccw(l.x, l.y, a) != -1) q.push_back(a);
        if (ccw(l.x, l.y, a)*ccw(l.x, l.y, b) < 0) {
            P p;
            crossLL(l, L(a, b), p);
            q.push_back(p);
        }
    }
    return q;
}



//0:P is out 1:P is on line 2:P is in
//高速化の余地があり
int contains(const Pol &pol, const L &l) {
    vector<P> v;
    v.push_back(l.x); v.push_back(l.y);
    for (int i = 0; i < (int)pol.size(); i++) {
        P a = cu(pol, i), b = cu(pol, i+1);
        P p;
        if (crossSS(L(a, b), l, p)) {
            v.push_back(p);
        }
    }

    sort(v.begin(), v.end(), [&](const P &x, const P &y){
        return abs(l.x-x) < abs(l.x-y);
    });

    int sz = (int)v.size();
    for (int i = 0; i < sz-1; i++) {
        v.push_back((v[i]+v[i+1])/(R)2);
    }
    bool f = false;
    for (P p: v) {
        int u = contains(pol, p); 
        if (!u) return 0;
        if (u == 2) f = true;
    }
    if (f) return 2;
    return 1;
}



R get(R x) {
    printf("? %.20lf\n", rad2deg(x));
    fflush(stdout);
    R r;
    scanf("%lf", &r);
    return r;
}

int main() {
    Pol p;
    p.push_back(P(-10000, -10000));
    p.push_back(P(+10000, -10000));
    p.push_back(P(+10000, +10000));
    p.push_back(P(-10000, +10000));
    const int N = 1000;
    for (int i = 0; i < N; i++) {
        R ar = 2*PI * i / N;
        R u = get(ar);
        L l = L(P(0,0), polar<R>(1.0, PI-ar));
        l.x += polar<R>(u, PI/2 - ar);
        l.y += polar<R>(u, PI/2 - ar);
        assert(p.size() >= 3);
        p = convex_cut(p, l);
        assert(p.size() >= 3);
        p.erase(unique(p.begin(), p.end(), [&](const P &l, const P &r){
            return near(l, r);
        }), p.end());
        if (near(p[0], p[p.size()-1])) p.pop_back();
        assert(p.size() >= 3);
//        for (P pp: p) {
//            cout << pp;
//        } cout << endl;
    }

    Pol r;
    for (int i = 0; i < (int)p.size(); i++) {
        P a = cu(p, i-1), b = cu(p, i), c = cu(p, i+1);
        R ar = radNorP(arg(a-b)-arg(c-b));
        ar = min(ar, 2*PI-ar);
        if (ar <= PI*171/180) {
            r.push_back(b);
        }
    }
    int st = -1;
    for (int i = 0; i < (int)r.size(); i++) {
        if (near(r[i], P(0, 0))) {
            st = i;
            break;
        }
    }
    assert(st != -1);
    printf("! %ld\n", r.size());
    for (int i = 0; i < (int)r.size(); i++) {
        P pp = cu(r, st+i);

        printf("! %d %d\n", (int)round(pp.real()), (int)round(pp.imag()));
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘R get(R)’:
./Main.cpp:397:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lf", &r);
                     ^

Judge Result