Submission #783103
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);
using namespace std;
namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9, PI = acos(-1.0);
typedef complex<double> P;
namespace std{
bool operator<(const P& a, const P& b){
return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}
}
typedef vector<P> G;
inline int xor128(){
//static int w = (unsigned int)time(NULL);
static int w = 88675123;
static int x = 123456789, y = 362436069, z = 521288629;
int t = x ^ x << 11;
x = y; y = z; z = w;
return w = w ^ w >> 19 ^ t ^ t >> 8;
}
inline double cross(const P& a, const P& b){ return imag(conj(a)*b); }
inline double dot(const P& a, const P& b){ return real(conj(a)*b); }
struct L : public vector<P>{
L(const P &a, const P &b) {
push_back(a); push_back(b);
}
};
inline int ccw(P a, P b, P c) {
b -= a; c -= a;
if(cross(b, c) > 0) return +1; // counter clockwise
if(cross(b, c) < 0) 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;
}
G convex_hull(G ps) {
int n = ps.size(), k = 0;
sort(ps.begin(), ps.end());
G ch(2*n);
for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
ch.resize(k-1);
return ch;
}
G input; int call = 0;
#if 0
inline double in(double x){
call++;
double mx = -INF; P r(cos(x), sin(x));
for(P p : input){ mx = max(mx, imag(p * r)); }
return mx;
}
#else
inline double in(double x){ printf("? %.12f\n", x*180/PI); fflush(stdout); double ymax; scanf("%lf", &ymax); return ymax; }
#endif
inline P solve(double t1, double y1, double t2, double y2){
double c1 = cos(t1), c2 = cos(t2);
double s1 = sin(t1), s2 = sin(t2);
if((s1 * c2 - s2 * c1) == 0) return P(INF, INF);
double x = (c2 * y1 - c1 * y2) / (s1 * c2 - s2 * c1);
double y = (s2 * y1 - s1 * y2) / (c1 * s2 - c2 * s1);
return P(x, y);
}
bool search(double t, P &res, const G &g, bool debug = 0){
double y = in(t), delta = 0.1;
if(y < EPS) return 0;
rep(it, 10){
double tt = t + delta, yy = in(tt), ycheck;
P p = solve(t, y, tt, yy), p2;
if(debug) dbg(p);
if(!(abs(p.real()) < 1001 && abs(p.imag()) < 1001)) goto NEXT;
p2 = p;
p.real((int)round(p.real()));
p.imag((int)round(p.imag()));
if(debug) dbg(p, p2, abs(abs(p - p2)) > EPS, abs(abs(p - p2)));
if(abs(abs(p - p2)) > 1e-5) goto NEXT;
rep(i, g.size()) if(abs(g[i] - p) < EPS) goto NEXT;
res = p;
return 1;
NEXT:
delta /= 5;
}
return 0;
}
G run(){
G g({P(0)});
set<P> use;
P p;
if(!search(PI + 0.01, p, g)){
search(PI + 0.01, p, g, 1);
dbg(input); P r(cos(PI+0.01), sin(PI+0.01));
for(P p : input) dbg(p * r);
assert(0);
}
g.pb(p);
int n = g.size();
while(1){
bool update = 0;
rep(i, n) if(!use.count(g[i])){
P res;
double a = -arg(g[(i + 1) % n] - g[i]);
if(search(a, res, g)){
g.pb(res);
update = 1;
n++;
break;
}
else if(search(a + PI, res, g)){
g.pb(res);
update = 1;
n++;
break;
}
else use.insert(g[i]);
}
sort(all(g), [](P a, P b){ return abs(a) < EPS || abs(b) < EPS ? abs(a) < abs(b) : arg(a) < arg(b);});
if(!update) break;
}
return g;
}
int main(){
#if 1
{
G g = run(); int n = g.size();
printf("! %d\n", n);
rep(i, n) printf("! %d %d\n", (int)(real(g[i])), (int)(imag(g[i]))); fflush(stdout);
}
#else
rep(it, 1000){
int n = xor128() % 1000 + 10;
G g;
rep(i, n){
int x = xor128() % 2001 - 1000;
int y = -(xor128() % 1000 + 1);
g.pb(P(x, y));
}
g.pb(P(0));
g = convex_hull(g);
input = g; call = 0;
G res = run();
sort(all(g)); sort(all(res));
if(g != res){
dbg(it, g.size(), res.size());
dbg(g); dbg(res);
//assert(0);
}
}
#endif
return 0;
}
Submission Info
Submission Time |
|
Task |
H - 回すだけ |
User |
nadeko |
Language |
C++11 (GCC 4.9.2) |
Score |
300 |
Code Size |
5453 Byte |
Status |
AC |
Exec Time |
58 ms |
Memory |
1956 KB |
Compile Error
./Main.cpp: In function ‘double in(double)’:
./Main.cpp:66:108: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
inline double in(double x){ printf("? %.12f\n", x*180/PI); fflush(stdout); double ymax; scanf("%lf", &ymax); return ymax; }
^
Judge Result
Set Name |
All |
Score / Max Score |
300 / 300 |
Status |
|
Set Name |
Test Cases |
All |
scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt |
Case Name |
Status |
Exec Time |
Memory |
scrambled_00.txt |
AC |
56 ms |
1812 KB |
scrambled_01.txt |
AC |
43 ms |
1828 KB |
scrambled_02.txt |
AC |
42 ms |
1824 KB |
scrambled_03.txt |
AC |
48 ms |
1820 KB |
scrambled_04.txt |
AC |
52 ms |
1808 KB |
scrambled_05.txt |
AC |
54 ms |
1824 KB |
scrambled_06.txt |
AC |
45 ms |
1812 KB |
scrambled_07.txt |
AC |
44 ms |
1824 KB |
scrambled_08.txt |
AC |
45 ms |
1816 KB |
scrambled_09.txt |
AC |
53 ms |
1956 KB |
scrambled_10.txt |
AC |
49 ms |
1816 KB |
scrambled_11.txt |
AC |
44 ms |
1856 KB |
scrambled_12.txt |
AC |
50 ms |
1832 KB |
scrambled_13.txt |
AC |
51 ms |
1816 KB |
scrambled_14.txt |
AC |
45 ms |
1808 KB |
scrambled_15.txt |
AC |
53 ms |
1780 KB |
scrambled_16.txt |
AC |
58 ms |
1820 KB |
scrambled_17.txt |
AC |
44 ms |
1816 KB |
scrambled_18.txt |
AC |
49 ms |
1892 KB |
scrambled_19.txt |
AC |
46 ms |
1868 KB |
scrambled_20.txt |
AC |
49 ms |
1820 KB |
scrambled_21.txt |
AC |
42 ms |
1804 KB |
scrambled_22.txt |
AC |
49 ms |
1788 KB |
scrambled_23.txt |
AC |
46 ms |
1824 KB |
scrambled_24.txt |
AC |
52 ms |
1824 KB |
scrambled_25.txt |
AC |
54 ms |
1824 KB |
scrambled_26.txt |
AC |
48 ms |
1820 KB |
scrambled_27.txt |
AC |
42 ms |
1828 KB |
scrambled_28.txt |
AC |
49 ms |
1832 KB |
scrambled_29.txt |
AC |
54 ms |
1824 KB |