#include #include #include using namespace std; const int MAX = 40000; struct Bod { double x; double y; }; struct Rovnice { double a; double b; }; struct Primka { Bod start; Bod konec; Rovnice rovnice; bool leziNa(double px, double py) const { if(start.x > konec.x) { if(((double)start.x < px) || ((double)konec.x > px)) return false; if(start.y > konec.y) { if(((double)start.y < py) || ((double)konec.y > py)) return false; } else { if(((double)start.y > py) || ((double)konec.y < py)) return false; } } else { if(((double)start.x > px) || ((double)konec.x < px)) return false; if(start.y > konec.y) { if(((double)start.y < py) || ((double)konec.y > py)) return false; } else { if(((double)start.y > py) || ((double)konec.y < py)) return false; } } return true; } void rovnice_primky() { double a = konec.y - start.y; double b = start.x - konec.x; rovnice.a = -(a / b); rovnice.b = -((-a * start.x - b * start.y) / b); //rovnice.a = (double)(start.x - konec.x) / (double)(start.y - konec.y); //rovnice.b = (double)(((-start.x + konec.x) * start.x) + ((-start.y + konec.y) * start.y)) / (double)(start.y - konec.y); //cout << "A:" << rovnice.a << "; B:" << rovnice.b << endl; } bool prusecik(const Primka &p) const { // Prusecik primek double px = (double)(p.rovnice.b - rovnice.b) / (double)(rovnice.a - p.rovnice.a); double py = (double)rovnice.a * px + (double)rovnice.b; //cout << "X:" << px << "; Y:" << py << endl; if(!leziNa(px, py)) return false; if(!p.leziNa(px, py)) return false; return true; } }; bool kriziSe(Primka *primky, int p, int n) // p je aktualni primka { if(p < 3) return false; // hledam pruseciky for(int i = p - 2; i >= n; i--) { if(primky[i].prusecik(primky[p])) { return true; } } return false; } int main() { /* Primka p1, p2; p1.start.x=1; p1.start.y=6; p1.konec.x=6; p1.konec.y=1; p2.start.x=2; p2.start.y=3; p2.konec.x=9; p2.konec.y=4; p1.rovnice_primky(); p2.rovnice_primky(); if(p1.prusecik(p2)) cout << "PRUSECIK" << endl; else cout << "HOVNO" << endl; return 1; */ int n; int p; Primka *primky = new Primka[MAX+1]; bool krizi; while(1) { cin >> n; if(n == 0) break; p = 0; krizi = false; cin >> primky[p].start.x >> primky[p].start.y; for(int i = 1; i < n; i++) { cin >> primky[p].konec.x >> primky[p].konec.y; if(!krizi) { primky[p].rovnice_primky(); krizi = kriziSe(primky, p, 0); // konec stary primky je zacatek novy primky primky[p+1].start.x = primky[p].konec.x; primky[p+1].start.y = primky[p].konec.y; p++; } } if(!krizi) { // spojit posledni bod s prvnim primky[p].konec.x = primky[0].start.x; primky[p].konec.y = primky[0].start.y; primky[p].rovnice_primky(); krizi = kriziSe(primky, p, 1); p++; } // if(krizi) cout << "NO\n"; else cout << "YES\n"; } delete [] primky; return 0; }