#include #include #include #include using namespace std; // Bod struct point { long long x, y; point(long long x=0, long long y=0) : x(x), y(y) {} }; // Operátor < na uspořádání bodů bool operator< (const point &A, const point &B) { return A.x < B.x || ( A.x == B.x && A.y < B.y ); } // Vektorový součin: vrátí >0 / 0 / <0 podle toho, zda OAB zatáčí proti směru // ručiček / jde rovně / zatáčí po směru long long cross(const point &O, const point &A, const point &B) { return (A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x); } // Skalární součin: pro O, A, B na přímce vrátí >0 jestliže jsou A a B // na stejné straně O, <0 jestliže jsou na opačných stranách long long dot(const point &O, const point &A, const point &B) { return (A.x-O.x)*(B.x-O.x)+(A.y-O.y)*(B.y-O.y); } // Konvexní obal pomocí Grahamova algoritmu; // předpokládá, že P je uspořádané zleva doprava vector convex_hull(vector P) { int n = P.size(), k = 0; vector H(2*n); for (int i = 0; i < n; i++) { while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--; H[k++] = P[i]; } for (int i = n-2, t = k+1; i >= 0; i--) { while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--; H[k++] = P[i]; } H.resize(k-1); return H; } // Binární vyhledávání: vrátí pořadové číslo úsečky, která určuje přímku obsahující // černý bod (řečený též sysel), resp. 0, pokud je černý bod vlevo, 10^8, jestliže // je vpravo long long binsrch(point& sysel, vector& hull, unsigned long long size) { if (cross(hull [0], hull [1], sysel) < 0) return 0; if (cross(hull [0], hull [size-1], sysel) > 0) return 1e8; long long lower = 1, upper = size - 1; while (upper - lower > 1) { if (cross(hull [0], hull [(lower+upper) / 2], sysel) > 0) lower = (lower + upper) / 2; else upper = (lower + upper) / 2; } return lower; } int main() { int N; cin >> N; vector P(N); for (int n=0; n> P[n].x >> P[n].y; sort(P.begin(), P.end()); vector hull = convex_hull(P); int Q; cin >> Q; point sysel; long long answer; for (int i = 0; i < Q; ++i) { cin >> sysel.x >> sysel.y; answer = binsrch(sysel, hull, hull.size()); if (answer == 0) { cout << hull [0].x << ' ' << hull [0].y << ' '; cout << hull [1].x << ' ' << hull [1].y << endl; } else if (answer == 1e8) { cout << hull [0].x << ' ' << hull [0].y << ' '; cout << hull.back().x << ' ' << hull.back().y << endl; } else if (cross(hull [answer], hull [answer + 1], sysel) < 0) { cout << hull [answer].x << ' ' << hull [answer].y << ' '; cout << hull [answer + 1].x << ' ' << hull [answer + 1].y << endl; } else { cout << "Primka neexistuje" << endl; } } return 0; }