#include #include #include #define CHILDREN 3 #define MAXAGE 1024 #define MAXN (CHILDREN*MAXAGE) #define EPS 0.00001 struct vector { double x, y; } vertices[CHILDREN]; struct candle { int id, angleid; double angle; } candles[CHILDREN][MAXN]; int N; double d; double angle (double x, double y, int v) { // kosinus uhlu je skalarni soucin podeleny soucinem velikosti double nx = x - vertices[v].x, ny = y - vertices[v].y, cosa; cosa = (nx*(-vertices[v].x+vertices[(v+CHILDREN-1)%CHILDREN].x) + ny*(-vertices[v].y+vertices[(v+CHILDREN-1)%CHILDREN].y)) / (d*hypot(nx, ny)); return sqrt(1-cosa*cosa); } int angle_cmp (struct candle *a, struct candle *b) { // kdyz se uhly lisi jen o velmi malo (EPS), jsou stejne if (a->angle - b->angle > EPS) return 1; if (b->angle - a->angle > EPS) return -1; return 0; } int intersection(struct vector s0, struct vector e0, struct vector s1, struct vector e1, struct vector s2, struct vector e2, struct vector *sv) { // v poradi Amin, Amax, Bmin, Bmax, Cmin, Cmax, a tady ulozime vysledek // nejsou to uhly, ale vektory nejakych svicek struct vector u, v, stp, endp; double t, sti, endi; u.x = s1.x - vertices[1].x; u.y = s1.y - vertices[1].y; v.x = s2.x - vertices[2].x; v.y = s2.y - vertices[2].y; t = (((vertices[1].x-vertices[2].x)/u.x)-((vertices[1].y-vertices[2].y)/u.y))/ (v.x/u.x - v.y/u.y); stp.x = vertices[2].x+t*v.x; stp.y = vertices[2].y+t*v.y; u.x = e1.x - vertices[1].x; u.y = e1.y - vertices[1].y; v.x = e2.x - vertices[2].x; v.y = e2.y - vertices[2].y; t = (((vertices[1].x-vertices[2].x)/u.x)-((vertices[1].y-vertices[2].y)/u.y))/ (v.x/u.x - v.y/u.y); endp.x = vertices[2].x+t*v.x; endp.y = vertices[2].y+t*v.y; v.x = endp.x - stp.x; v.y = endp.y - stp.y; u.x = s0.x; u.y = s0.y; t = (stp.y / u.y - stp.x / u.x) / (v.x / u.x - v.y / u.y); if (t < 0) sti = 0; else if (t > 1) sti = 1; else sti = t; u.x = e0.x; u.y = e0.y; t = (stp.y / u.y - stp.x / u.x) / (v.x / u.x - v.y / u.y); if (t < 0) endi = 0; else if (t > 1) endi = 1; else endi = t; if (sti > endi) { t = sti; sti = endi; endi = t; } if (sti + EPS > endi) return 0; t = (sti + endi) / 2; sv->x = stp.x + t*v.x; sv->y = stp.y + t*v.y; return 1; } int main (void) { int i, j, k; struct vector vcandles[MAXN]; int dangles[CHILDREN], angles[CHILDREN][MAXN]; int position[CHILDREN][MAXN], anglespart[CHILDREN-1][MAXN]; int st[CHILDREN-1], end[CHILDREN-1], cnt[CHILDREN - 1]; struct vector sv; // Inicializace, nacteni vstupu scanf("%lf%d", &d, &N); vertices[0].x = 0; vertices[0].y = 0; vertices[1].x = d; vertices[1].y = 0; vertices[2].x = d/2; vertices[2].y = sqrt(3)*d/2; for (i = 0; i < N; i++) { scanf("%lf%lf", &vcandles[i].x, &vcandles[i].y); for (j = 0; j < CHILDREN; j++) { candles[j][i].id = i; candles[j][i].angle = angle(vcandles[i].x, vcandles[i].y, j); } } // Setrizeni podle uhlu z jednotlivych vrcholu for (j = 0; j < CHILDREN; j++) qsort(candles[j], N, sizeof(struct candle), (int (*)(const void *, const void *))angle_cmp); // Pole ruznych uhlu z ednotlivych vrcholu, useky stejnych uhlu, ... for (j = 0; j < CHILDREN; j++) dangles[j] = 1 + (*angles[j] = 0); for (j = 0; j < CHILDREN; j++) for (i = 1; i < N; i++) { if (angle_cmp(&candles[j][i], &candles[j][i-1])) angles[j][dangles[j]++] = i; candles[j][i].angleid = dangles[j]-1; } for (j = 0; j < CHILDREN; j++) angles[j][dangles[j]] = N; // Zapamatovani si pozic vicek v setrizenych polich for (j = 0; j < CHILDREN; j++) for (i = 0; i < N; i++) position[j][candles[j][i].id] = i; // Pocatecni nastaveni poctu svicek v jednotlivych castech (podle deleni z A) for (j = 1; j < CHILDREN; j++) for (i = 0; i < dangles[j]; i++) anglespart[j-1][i] = (j - 1)?0:(angles[j][i+1] - angles[j][i]); // Vypocet for (i = 0; i < dangles[0] - 1; i++) { // Prepocitani poctu svicek s jednotlivymi uhly v jednotlivych castech for (j = angles[0][i]; j < angles[0][i+1]; j++) { anglespart[0][candles[1][position[1][candles[0][j].id]].angleid]--; anglespart[1][candles[2][position[2][candles[0][j].id]].angleid]++; } // Hledani zacatku a konce intervalu pro B a C // Vrchol B cnt[0] = k = 0; while (k < dangles[1] && cnt[0] < N/3) cnt[0] += anglespart[0][k++]; if (cnt[0] != N/3) goto nextloop; st[0] = k-1; while (k < dangles[1] && !anglespart[0][k]) k++; end[0] = k < dangles[1] ? k: k-1; // Vrchol C cnt[1] = 0; k = dangles[2] - 1; while (k >= 0 && cnt[1] < N/3) cnt[1] += anglespart[1][k--]; if (cnt[1] != N/3) goto nextloop; end[1] = k+1; while (k >= 0 && !anglespart[1][k]) k--; st[1] = k >= 0? k: k+1; if (intersection(vcandles[candles[0][angles[0][i]].id], vcandles[candles[0][angles[0][i+1]].id], vcandles[candles[1][angles[1][st[0]]].id], vcandles[candles[1][angles[1][end[0]]].id], vcandles[candles[2][angles[2][st[1]]].id], vcandles[candles[2][angles[2][end[1]]].id], &sv)) { printf("%lf %lf\n", sv.x, sv.y); return 0; } nextloop: } printf("No solution\n"); return 0; }