#include #include using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; typedef long double ld; const ll nils = 1000000007; template int sgn(T x) { return (x > 0) - (x < 0); } template struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [-pi, pi] double angle() const { return atan2(y, x); } P unit() const { return *this/dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << "," << p.y << ")"; } }; typedef Point P; vector

convexHull(vector

pts) { if (sz(pts) <= 1) return pts; sort(all(pts)); vector

h(sz(pts)+1); int s = 0, t = 0; for (int it = 2; it--; s = --t, reverse(all(pts))) for (P p : pts) { while (t >= s + 2 && h[t-2].cross(h[t-1], p) <= 0) t--; h[t++] = p; } return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])}; } template bool onSegment(P s, P e, P p) { return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0; } template vector

segInter(P a, P b, P c, P d) { auto oa = c.cross(d, a), ob = c.cross(d, b), oc = a.cross(b, c), od = a.cross(b, d); // Checks if intersection is single non-endpoint point. if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0) return {(a * ob - b * oa) / (ob - oa)}; set

s; if (onSegment(c, d, a)) s.insert(a); if (onSegment(c, d, b)) s.insert(b); if (onSegment(a, b, c)) s.insert(c); if (onSegment(a, b, d)) s.insert(d); return {all(s)}; } template T polygonArea2(vector>& v) { T a = v.back().cross(v[0]); rep(i,0,sz(v)-1) a += v[i].cross(v[i+1]); return a; } double dist(P p1, P p2){ P q = p1-p2; return q.dist(); } int n,m; string mode; int MAXX = 1000; void print_pts(P p1, P p2){ cout << p1.x << " " << p1.y << " " << p2.x << " " << p2.y << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> mode; if(mode == "hourglass"){ ll mid_x = MAXX/2; ll mid_y = MAXX/2; P mid(mid_x, mid_y); vector > ans; vi x_coords; rep(c1,0,n/2){ x_coords.push_back((2*(c1+1)*MAXX) / n); } rep(c1,0,n/2-1){ int x1 = x_coords[c1]; int x2 = x_coords[c1+1]; ans.push_back({P(x1, MAXX-1), P(x2, MAXX-1)}); ans.push_back({P(x1, 1), P(x2, 1)}); } rep(c1,0,n/2){ ans.push_back({mid, P(x_coords[c1], MAXX-1)}); ans.push_back({mid, P(x_coords[c1], 1)}); } random_shuffle(all(ans)); cout << sz(ans) << "\n"; trav(p, ans){ print_pts(p.first, p.second); } } if(mode == "circle"){ ll mid_x = MAXX/2; ll mid_y = MAXX/2; double r = MAXX/2-5; double pi = acos(-1); int segs = 0; vector > ans; vector

pts; rep(c1,0,n){ double v = 2.0 * pi * double(c1) / double(n); pts.push_back(P(mid_x + ll(r*cos(v)), mid_y + ll(r*sin(v)))); } vi sequence; rep(c1,0,n){ ans.push_back({pts[c1], pts[(c1+1)%n]}); segs++; sequence.push_back(c1); } while(sz(sequence) > 3 && segs < m){ vi new_segs; int prev = 0; new_segs.push_back(sequence[0]); rep(c1,1,sz(sequence)-1){ if(rand()%2 == 0 && c1 != prev+1 && dist(pts[sequence[prev]],pts[sequence[c1]]) > 100 && segs < m){ ans.push_back({pts[sequence[prev]], pts[sequence[c1]]}); prev = c1; segs++; new_segs.push_back(sequence[c1]); } } sequence = new_segs; } cout << sz(ans) << "\n"; trav(p, ans){ print_pts(p.first, p.second); } } if(mode == "convex"){ vector

pts; set S; map M; vector > ans; rep(c1,0,n){ ll x = rand()%MAXX; ll y = rand()%MAXX; while(S.find({x, y}) != S.end()){ x = rand()%MAXX; y = rand()%MAXX; } S.insert({x, y}); pts.push_back(P(x, y)); } sort(all(pts)); rep(c1,0,n){ M[pts[c1]] = c1; } rep(c1,0,n-1){ ans.push_back({pts[c1], pts[c1+1]}); } vector

conv = convexHull(pts); vi ind; trav(p, conv){ ind.push_back(M[p]); } rep(c1,0,sz(ind)){ int i = ind[c1]; int j = ind[(c1+1)%sz(ind)]; if(abs(i-j) != 1){ ans.push_back({pts[i], pts[j]}); } } cout << sz(ans) << "\n"; trav(p, ans){ print_pts(p.first, p.second); } } return 0; }