#include #include #include // Pomocné funkce typedef struct vector { double x; double y; } vector; #define VERT(cont,i) i2v(cont[2*(i)],cont[2*(i)+1]) #define VECTOR(ci,i,cj,j) sub(VERT(ci,i),VERT(cj,j)) #define v2i(a) (a).x, (a).y // Dvě čísla => vektor static inline vector i2v(double x, double y) { vector out = { x, y }; return out; } // Normálový vektor static inline vector norm(vector a) { vector out = { -a.y, a.x }; return out; } // Odečtení vektorů static inline vector sub(vector a, vector b) { vector out = { (a.x-b.x), (a.y - b.y) }; return out; } // Kladné, je-li a vpravo od b, jinak záporné static inline double right_of(vector a, vector b) { return ((a.x)*(b.y) - (a.y)*(b.x)); } // Skalární součin static inline double dotproduct(vector a, vector b) { return (a.x*b.x + a.y*b.y); } // Délka vektoru static inline double len(vector a) { return sqrt(dotproduct(a,a)); } // Pata výšky v trojúhelníku static inline vector altfoot(vector a, vector b, vector p) { double dx = b.x - a.x; double dy = b.y - a.y; vector out = { (dx*dy*(p.y - a.y) + dx*dx*p.x + dy*dy*a.x)/(dx*dx + dy*dy), (dx*dy*(p.x - a.x) + dx*dx*a.y + dy*dy*p.y)/(dx*dx + dy*dy) }; return out; } int A, E; double *a, *e; // vstupní data int as = 1, es = 1; // -1, je-li kontinent zadán opačně, než předpokládáme int amin = -1, emin = -1; double distmin = INFINITY; // ukládáme nejkratší vzdálenost mezi vrcholy int main(void) { scanf("%d", &A); // Amerika a = calloc(2*A, sizeof(double)); for (int i=0;i<2*A;i++) scanf("%lf", a + i); scanf("%d", &E); // Evropa e = calloc(2*E, sizeof(double)); for (int i=0;i<2*E;i++) scanf("%lf", e + i); if ((A < 3) || (E < 3)) { // Kontrola počtu vrcholů printf("Malo vrcholu na polygon.\n"); return 1; } // Kontrola orientace if (right_of(VECTOR(a,0,a,1), VECTOR(a,1,a,2)) < 0) as = -1; if (right_of(VECTOR(e,0,e,1), VECTOR(e,1,e,2)) < 0) es = -1; // Najdeme vrchol(y) nejvíce vlevo/nejvíce vpravo // Začneme totiž ve vodorovném směru int ai = 0, ei = 0; if (a[0] < a[2]) { ai = 1; while (a[2*ai] < a[2*(ai+1)]) ai++; } else if (a[0] < a[2*(E-1)]) { ai = A-1; while (a[2*ai] < a[2*(ai-1)]) ai--; } if (e[0] > e[2]) { ei = 1; while (e[2*ei] > e[2*(ei+1)]) ei++; } else if (e[0] > e[2*(E-1)]) { ei = E-1; while (e[2*ei] > e[2*(ei-1)]) ei--; } for (int i=0;i 0) { // Přímka ztotožněna s nějakou hranou E int t=ei; ei += E + es; ei %= E; if (( right_of(VECTOR(a,ai,e,ei), norm(VECTOR(e,ei,e,t))) * right_of(VECTOR(a,ai,e,t), norm(VECTOR(e,ei,e,t))) < 0) && dotproduct(VECTOR(a,ai,e,ei), norm(VECTOR(e,ei,e,t))) < 0) { vector out = altfoot(VERT(e,ei), VERT(e,t), VERT(a,ai)); printf("%lf %lf\n%lf %lf\n", v2i(VERT(a,ai)), v2i(out)); return 0; } } else { // Přímka ztotožněna s nějakou hranou A int t=ai; ai += A + as; ai %= A; if (( right_of(VECTOR(e,ei,a,ai), norm(VECTOR(a,ai,a,t))) * right_of(VECTOR(e,ei,a,t), norm(VECTOR(a,ai,a,t))) < 0) && dotproduct(VECTOR(e,ei,a,ai), norm(VECTOR(a,ai,a,t))) < 0) { vector out = altfoot(VERT(a,ai), VERT(a,t), VERT(e,ei)); printf("%lf %lf\n%lf %lf\n", v2i(VERT(e,ei)), v2i(out)); return 0; } } } // Nebyla nalezena kombinace vrchol-hrana, vypíšeme vrchol-vrchol printf("%lf %lf\n%lf %lf\n", v2i(VERT(a,amin)), v2i(VERT(e,emin))); }