#include #define endl '\n' #define pb push_back using namespace std; const int MAX_N = 105, MAX_M = 15; double angle; struct Point { int x, y; Point(){} Point(int x, int y) { this->x = x; this->y = y; } bool operator< (const Point &other) const { if(x == other.x) { return y < other.y; } double a = tan(angle), b1, b2; b1 = y - a * x; b2 = other.y - a * other.x; double p1, p2; p1 = -b1 / a; p2 = -b2 / a; return p1 > p2; } bool operator<= (const Point &other) const { if(x == other.x) { return y <= other.y; } double a = tan(angle), b1, b2; b1 = y - a * x; b2 = other.y - a * other.x; double p1, p2; p1 = -b1 / a; p2 = -b2 / a; return p1 >= p2; } }; Point ps[MAX_N], st[MAX_N], lp, np, fp; vector mt, mk; vector mp1, mp2; double dist(Point a, Point b) { return sqrt((double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y)); } bool is_out(Point p) { if(p.x < 0 || p.x > 1000 || p.y < 0 || p.y > 700) { return true; } else { return false; } } Point is_pos_first(Point p, Point q) { int x, y; if(p.x != q.x) { x = 3 * p.x - 2 * q.x; y = 3 * p.y - 2 * q.y; } else { x = p.x; y = 3 * p.y - 2 * q.y; } np = Point(x, y); return np; } double calc_dist_between_lines(Point p1, Point p2) { double a, b1, b2; a = tan(angle); b1 = p1.y - a * p1.x; b2 = p2.y - a * p2.x; double y = b1; double yy = b2; double x = (y - b2) / a; double d = sqrt(dist(Point(0, yy), Point(x, 0))); return abs(yy - y) * abs(x) / d; } int main() { freopen("geometry.in", "r", stdin); freopen("geometry.out", "w", stdout); double e_powers[25]; e_powers[0] = 1; for(int i = 1; i <= 20; i++) { e_powers[i] = e_powers[i - 1] * (2.71 / 2.0); } ios_base::sync_with_stdio(false); cin.tie(NULL); double curr_time, start_time; start_time = clock(); cout<>n; for(int i = 0; i < n; i++) { int x, y; cin>>x>>y; ps[i] = Point(x, y); } int m; cin>>m; for(int i = 0; i < m; i++) { int x, y; cin>>x>>y; st[i] = Point(x, y); } double curr_ans = 1000000, angle_ans; vector ans_t, ans_k; vector ans_p1, ans_p2; for(int i = 0; i <= 31400; i += 2) { curr_time = clock(); if((double)curr_time - (double)start_time >= 4500) { break; } angle = i / 10000.0; mt.clear(); mk.clear(); mp1.clear(); mp2.clear(); set sorted; for(int j = 0; j < n; j++) { sorted.insert(ps[j]); if(j == 0 || lp < ps[j]) { lp = ps[j]; } } int cost = 0, cnt_out = 0; while(1) { Point tmp = *sorted.begin(); bool has_change = false, is_pos = false; Point other, curr_best_np = tmp, other1; for(set::iterator it = sorted.end(); it != sorted.begin(); it--) { if(it == sorted.begin()) { continue; } if(!(tmp < *it)) { continue; } Point p = is_pos_first(*it, tmp); if(p < lp && tmp < p) { if(is_out(p)) { is_pos = true; other = *it; } else { has_change = true; if(curr_best_np < p) { curr_best_np = p; other1 = *it; } } } } if(!has_change) { if(!is_pos || cnt_out == 20) { break; } else if(is_pos) { mt.pb(1); mk.pb(-2); mp1.pb(other); mp2.pb(tmp); cnt_out++; } } else { sorted.insert(curr_best_np); mt.pb(1); mk.pb(-2); mp1.pb(other1); mp2.pb(tmp); } sorted.erase(sorted.begin()); } Point p = *sorted.begin(); double dis = calc_dist_between_lines(p, lp); double total = 25 * (dis + (dis + 1) * e_powers[cnt_out] / 100.0) + cost * (dis + 1) / 50; if(total < curr_ans) { angle_ans = angle; curr_ans = total; ans_t.clear(); ans_k.clear(); ans_p1.clear(); ans_p2.clear(); for(int j = 0; j < mt.size(); j++) { ans_t.pb(mt[j]); if(mt[j] == 1) { ans_k.pb(mk[j]); } ans_p1.pb(mp1[j]); if(mt[j] != 3) { ans_p2.pb(mp2[j]); } } } for(int j = 0; j < m; j++) { Point p = *sorted.begin(); if(p < st[j] && st[j] < lp) { cost += 15; sorted.erase(sorted.begin()); sorted.insert(st[j]); mt.pb(3); mp1.pb(p); } } p = *sorted.begin(); dis = calc_dist_between_lines(p, lp); total = 25 * (dis + (dis + 1) * e_powers[cnt_out] / 100.0) + cost * (dis + 1) / 50; if(total < curr_ans) { angle_ans = angle; curr_ans = total; ans_t.clear(); ans_k.clear(); ans_p1.clear(); ans_p2.clear(); for(int j = 0; j < mt.size(); j++) { ans_t.pb(mt[j]); if(mt[j] == 1) { ans_k.pb(mk[j]); } ans_p1.pb(mp1[j]); if(mt[j] != 3) { ans_p2.pb(mp2[j]); } } } } cout<