#include #include #include #include typedef long double ld; #define M_PIl 3.1415926535897932384626433832795029L #define EPSILON 0.000000001 struct point { long double x; long double y; int pos; }; typedef struct point point; struct line { long double a; long double b; long double c; }; typedef struct line line; int m,n; point CNT; /* aktuální střed */ /* Spočítá koeficienty rovnice přímky pro dva zadané body. */ void getcoord(line *l, point one, point two) { if (one.x == two.x) { l->a = 1; l->b = 0; l->c = -one.x; } else { l->b = -1; l->a = (two.y - one.y) / (long double) (two.x - one.x); l->c = -(l->a)*one.x + one.y; } } /* Spočítá úhel pro rotování přímkou. */ ld linearc(long double y, long double x) { ld r = atan2l(y,x); r = ((r<=0) ? (M_PIl + r) : r); return r; } /* Porovnávací funkce pro třízení dle úhlů. */ int arcompare(const void *aa, const void *bb) { point * a, *b; a = (point *) aa; b = (point*)bb; ld ar = linearc(a->y - CNT.y, a->x - CNT.x); ld br = linearc(b->y - CNT.y, b->x - CNT.x); if (fabsl(ar-br) < EPSILON) return 0; else return (ar= 2*m) ls[1]++; else if (one.pos < 2*m) rs[0]++; else rs[1]++; if (ls[0] < rs[0] && two.pos < 2*m) ls[0]++; else if (ls[1] < rs[1] && two.pos >= 2*m) ls[1]++; else if (two.pos < 2*m) rs[0]++; else rs[1]++; if (ls[0] == rs[0] && (ls[0] == m) && ls[1] == rs[1] && (ls[1] == n)) { return 1; } return 0; } /* Zkontroluje, je-li přímka skutečně řešením. */ int solution(line l, point *s) { int ls[2] = {0}; int rs[2] = {0}; ld r; for (int i=0; i<2*m + 2*n; i++) { r = (l.a * s[i].x) + (l.b * s[i].y) + l.c; if (fabsl(r) < EPSILON) return 0; if (r < 0) ls[s[i].pos >= 2*m]++; else rs[s[i].pos >= 2*m]++; } if (ls[0] == rs[0] && (ls[0] == m) && ls[1] == rs[1] && (ls[1] == n)) { return 1; } return 0; } /* Posune přímku o malý kousek, aby se stala řešením. */ void wiggle(line *l, point one, point two, int *hint) { ld zy = one.y - two.y, zx = one.x - two.x; /* Před posunutím převedeme kolmý vektor na jednotkovou velikost. */ ld norm = sqrtl(zy*zy + zx*zx); point pa, pb; pa.x = one.x + (-20*EPSILON * hint[0] * (zy/norm)); pa.y = one.y + (20*EPSILON * hint[0] * (zx/norm)); pb.x = two.x + (-20*EPSILON * hint[1] * (zy/norm)); pb.y = two.y + (20*EPSILON * hint[1] * (zx/norm)); getcoord(l, pa, pb); } int main(void) { FILE *fin, *fout; point *s, *sd; fin = fopen("plan.in", "r"); fout = fopen("primka.out", "w"); fscanf(fin, "%d %d\n", &m, &n); m /= 2; n /= 2; s = malloc(2*(m+n)*sizeof(point)); // Kopie pole 's' pro třídící účely. sd = malloc(2*(m+n)*sizeof(point)); int hint[2] = {0}; int rs[2] = {0}; int ls[2] = {0}; int j; line l; for (int i=0; i<2*(m+n); i++) { fscanf(fin, "%Lf %Lf\n", &(s[i].x), &(s[i].y)); s[i].pos = sd[i].pos = i; sd[i].x = s[i].x; sd[i].y = s[i].y; } for (int i=0; i<2*(m+n); i++) { j = 0; hint[0] = hint[1] = rs[0] = ls[0] = rs[1] = ls[1] = 0; /* Nastavíme střed, setřídíme. */ CNT.x = s[i].x; CNT.y = s[i].y; qsort(sd, 2*(m+n), sizeof(point), arcompare); if ((sd[j].x == CNT.x) && (sd[j].y == CNT.y)) j++; getcoord(&l, s[i], sd[j]); /* Pro první dvojici napočítáme lineárně. */ for (int k=0; k<2*(m+n); k++) { if ( (s[k].x == CNT.x && s[k].y == CNT.y) || (s[k].x == sd[j].x && s[k].y == sd[j].y)) continue; if ( (l.a*s[k].x + l.b*s[k].y + l.c) > EPSILON) rs[(s[k].pos>=2*m)]++; else ls[(s[k].pos>=2*m)]++; } /* Pro zbylé dvojice s tímto bodem konstantně. */ do { if (pseudosolution(s[i], sd[j], ls, rs)) { /* Zkusí všechny čtyři možnosti, jak zakvedlat body. */ for (hint[0] = -1; hint[0] < 2; hint[0] += 2) for (hint[1] = -1; hint[1] < 2; hint[1] += 2) { wiggle(&l, s[i], sd[j], hint); if (solution(l, s)) { fprintf(fout, "%.15Lf %.15Lf %.15Lf\n", l.a, l.b, l.c); return 0; } } /* Nestane se. */ return -1; } else { if (((sd[j].y - CNT.y) < 0) || ((sd[j].y - CNT.y == 0) && (sd[j].x - CNT.x > 0))) ls[sd[j].pos >= 2*m]++; else rs[sd[j].pos >= 2*m]++; /* Načti nový bod. */ j++; /* While cyklus končí zde. */ if (j>=2*(m+n)) break; if (((sd[j].y - CNT.y) < 0) || ((sd[j].y - CNT.y == 0) && (sd[j].x - CNT.x > 0))) rs[sd[j].pos >= 2*m]--; else ls[sd[j].pos >= 2*m]--; } } while (1); } return 0; }