#include #include #include #define MAX_N 1024 #define INF 1000000 typedef struct{ float x, y; }t_point; typedef struct{ t_point max, min; float x, y; }t_edge; int n, ne, nb[MAX_N]; t_point p[MAX_N]; t_edge e[MAX_N]; int b[MAX_N][MAX_N]; float minDiff; int return_value(float a) { if (a > 0) return 1; if (a < 0) return -1; return 0; } int cmp(const void *a, const void *b) { t_point k, l; k = *(t_point *)a; l = *(t_point *)b; return return_value(k.y - l.y); } int cmp_edge(t_edge *p, t_edge *q) { float t1, t2; if (p->min.y > q->max.y || p->max.y < q->min.y){ return 0; }else{ if (p->max.y > q->max.y){ t1 = ((q->max.y - minDiff/2) - p->min.y) / p->y; t2 = ((q->max.y - minDiff/2) - q->min.y) / q->y; return return_value(p->x*t1 + p->min.x - (q->x*t2 + q->min.x)); }else{ t1 = ((p->max.y - minDiff/2) - q->min.y) / q->y; t2 = ((p->max.y - minDiff/2) - p->min.y) / p->y; return return_value(p->x*t2 + p->min.x - (q->x*t1 + q->min.x)); } } } void sort_edges(void) { int less_cnt[MAX_N]; int greater_cnt[MAX_N]; int greater[MAX_N][MAX_N]; int smallest[MAX_N]; int i, j, smallest_cnt = 0; t_edge sortede[MAX_N]; for (i = 0; i < ne; i++) { less_cnt[i] = 0; for (j = 0; j < ne; j++) if (j != i && cmp_edge(&e[j], &e[i]) < 0) { less_cnt[i]++; greater[j][greater_cnt[j]++] = i; } if (!less_cnt[i]) smallest[smallest_cnt++] = i; } for (i = 0; i < smallest_cnt; i++) { sortede[i] = e[smallest[i]]; for (j = 0; j < greater_cnt[smallest[i]]; j++) { less_cnt[greater[smallest[i]][j]]--; if (less_cnt[greater[smallest[i]][j]] == 0) smallest[smallest_cnt++] = greater[smallest[i]][j]; } } for (i = 0; i < ne; i++) e[i] = sortede[i]; } int bs(float y, int z, int k) { int i = (z + k) / 2; if (k < 0 || z >= n) return -1; if (p[i].y > y) return bs(y, z, i-1); if (i+1 < n && p[i+1].y <= y) return bs(y, i+1, k); return i; } int bsearch_edge(float x, float y, int pas, int z, int k) { t_edge e1, e2; float t1, t2; int i = (z + k) / 2; if (i+1 >= nb[pas]) return 0; e1 = e[b[pas][i]]; e2 = e[b[pas][i+1]]; t1 = (y - e1.min.y) / e1.y; t2 = (y - e2.min.y) / e2.y; if (k < 0 || z >= n) return 0; if (e1.x*t1 + e1.min.x > x) return bsearch_edge(x, y, pas, z, i-1); if (e2.x*t2 + e2.min.x < x) return bsearch_edge(x, y, pas, i+1, k); return !(i % 2); } int in(float x, float y) { int pas; pas = bs(y, 0, n - 1); if (pas >= 0 && bsearch_edge(x, y, pas, 0, nb[pas] - 1)){ return 1; }else return 0; } int main(void) { int i, i1, i2, j, m, max, min; float x, y, medy; scanf("%d", &n); for (i=0; i p[i2].y){ max = i1; min = i2; }else{ max = i2; min = i1; } e[ne].max = p[max]; e[ne].min = p[min]; e[ne].x = p[max].x - p[min].x; e[ne++].y = p[max].y - p[min].y; } } qsort(p, n, sizeof(t_point), cmp); /* ruseni spatnych vrcholu */ for (i=0, j=0; i= n || p[i].y != p[i+1].y){ p[j++] = p[i]; } } n = j; minDiff = INF; for (i=0; i e[j].min.y && medy < e[j].max.y){ b[i][nb[i]++] = j; } } } scanf("%d", &m); for (i=0; i