#include #include class CPoint { /* Třida reprezentující body */ public: double x,y; /* Souřadnice bodu */ void input(); /* Načtení dat ze vstupu */ }; class CLine { /* Pomocná třída reprezentující přímku či úsečky, která nesmí být svislá. */ CPoint *A,*B; /* Zadána dvěma body */ double a,b,c; /* Předpočítaná data */ public: CLine(CPoint &A, CPoint &B); /* Základní konstruktor */ int upperThanLine(CPoint &pt); /* Leží bod nad nebo pod přímkou? */ int isBetween(CPoint &pt); /* Leží bod uvnitř úsečky (pokud je na přímce)? */ }; class CPolygon { /* Mnohoúhelník */ public: int n; /* Počet vrcholů */ CPoint *pt; /* Jednotlivé vrcholy (alokováno dynamicky) */ CPolygon(); /* Konstruktor: načtení */ ~CPolygon(); /* Destruktor */ }; class CSortedPoly { /* Indexy bodů mnohoúhelníka setřiděné podle $x$ */ CPolygon *p; public: int *index; /* Přístup řeší konstruktor a přetížený operátor $[]$ */ CSortedPoly(CPolygon &poly); ~CSortedPoly(); CPoint &operator [] (int i) {return p->pt[index[i]];}; }; class CCutPoints { /* Třída reprezentující ``plátky'' */ public: CPolygon *p; int cnt; /* Počet plátků */ int or; /* Orientace mnohoúhelníka */ double dif; /* Tloušťka plátku */ int *upper, *lower; /* Pro každý plátek horní a dolní hranice mnohoúh. */ int maxlow, maxup; CCutPoints(CPolygon& poly); ~CCutPoints(); }; class CProblem { /* Třída řešící naši úlohu */ CPolygon *p; CCutPoints *c; /* Konstruktor -- předpočítá data */ public: CProblem(); ~CProblem(); int solve(CPoint &X); /* Určí, zda $X$ je uvnitř $P$ */ }; int main(void) { CProblem p; CPoint X; for(;;) { cout << "Zadej bod:"; X.input(); if (p.solve(X)) cout << "Lezi uvnitr\n"; else cout << "Lezi vne\n"; if ((X.x==0) && (X.y==0)) break; } return 0; } void CPoint::input() { cin >> x >> y; } CLine::CLine(CPoint &A, CPoint &B) { if (A.xA = &A; this->B = &B; } else { this->B = &A; this->A = &B; } a = A.y - B.y; b = B.x - A.x; c = -( a*A.x + b*A.y); } int CLine::upperThanLine(CPoint &pt) { double x = a*pt.x + b*pt.y +c; if (x>0) return 1; if (x<0) return -1; return 0; } int CLine::isBetween(CPoint &pt) { return ((A->x<=pt.x) && (B->x>=pt.x)); } CPolygon::CPolygon() { cin >> n; pt = new CPoint[n]; for (int i=0;ipt[*(int *)a]).x < (__poly->pt[*(int *)b]).x) return -1; if ((__poly->pt[*(int *)a]).x > (__poly->pt[*(int *)b]).x) return 1; return 0; } CSortedPoly::CSortedPoly(CPolygon &poly) { p = &poly; __poly = p; index = new int[p->n]; for (int i=0;i < p->n;i++) index[i]=i; qsort(index, p->n, sizeof(int), cmpInd); } CSortedPoly::~CSortedPoly() { delete[] index; } CCutPoints::CCutPoints(CPolygon &poly) { p = &poly; CSortedPoly s(poly); double minDif=s[p->n -1].x - s[0].x; /* Nejmenší rozdíl $x$ */ int i; for(i=0;i < p->n -1;i++) { dif = s[i+1].x-s[i].x; if (dif>0) /* dif == 0 není zajímavý */ if (difn -1].x - s[0].x)/minDif)+1; /* Počet dílků */ lower = new int[cnt]; upper = new int[cnt]; int ptr; if (s[0].x == s[1].x) { /* Vytvoření dílků */ if (s[0].yn -1].x == s[p->n -2].x) { if (s[p->n -1].yn -2].y) { maxlow=s.index[p->n -1]; maxup=s.index[p->n -2]; } else { maxlow=s.index[p->n -2]; maxup=s.index[p->n -1]; } } else { maxlow=maxup=s.index[p->n -1]; } for(i=1;ipt[upper[i-1]],p->pt[maxup]) .upperThanLine(s[ptr])>0) { /* Tento bod je nahoře */ upper[i]=s.index[ptr]; } else lower[i]=s.index[ptr]; /* Bod je dole */ ptr++; continue; /* Zkusíme další */ } break; /* Neležel tam tento, nebude tam žádný další */ } } } CCutPoints::~CCutPoints() { delete[] lower; delete[] upper; } CProblem::CProblem() { p = new CPolygon(); c = new CCutPoints(*p); } CProblem::~CProblem() { delete c; delete p; } int CProblem::solve(CPoint &X) { if ( p->pt[c->lower[0]].x==X.x /* Neleží náhodou na levé či pravé hranici? */ && p->pt[c->lower[0]].y<=X.y && p->pt[c->upper[0]].y>=X.y) return 1; if ( p->pt[c->maxlow].x==X.x && p->pt[c->maxlow].y<=X.y && p->pt[c->maxup].y>=X.y) return 1; int cut = (int)((X.x- (p->pt[c->lower[0]]).x)/c->dif); if (cut<0 || cut>=c->cnt) return 0; /* Mimo hranice $x$ */ /* Leží pod/nad přímkami? */ if ((CLine(p->pt[c->upper[cut]],p->pt[(c ->upper[cut]+p->n+c->or)%(p->n)]).upperThanLine(X)<=0) && (CLine(p->pt[c->lower[cut]],p->pt[(c ->lower[cut]+p->n-c->or)%(p->n)]).upperThanLine(X)>=0) && (cut+1 == c->cnt || ((CLine(p->pt[c->upper[cut+1]],p->pt[(c ->upper[cut+1]+p->n+c->or)%(p->n)]).upperThanLine(X)<=0) && (CLine(p->pt[c->lower[cut+1]],p->pt[(c ->lower[cut+1]+p->n-c->or)%(p->n)]).upperThanLine(X)>=0)))) return 1; return 0; }