#include #include #include using namespace std; #define REPI(ctr,start,limit) for (int32_t ctr=(start);(ctr)<(limit);(ctr)++) struct Point { double x,y; explicit Point(double _x=0,double _y=0) { x = _x; y = _y; } double operator*(Point p) const { return x * p.y - y * p.x; } Point operator*(double r) const { return Point(x*r,y*r); } Point operator+(Point p) const { return Point(x+p.x,y+p.y); } Point operator-(Point p) const { return Point(x-p.x,y-p.y); } bool operator==(Point p) const { return x == p.x && y == p.y; } }; //bool intersect(Point p0,Point p1,Point q0,Point q1) { // Point // r = p1 - p0, // s = q1 - q0, // v = q0 - p0; // // double // d = r * s, // t = (v * s) / d, // u = (v * r) / d; // // if (d == 0) { // if (v * r == 0) { // t = (v.x * r.x + v.y * r.y) / (r.x * r.x + r.y * r.y); // u = t + (s.x * r.y + s.y * r.y) / (r.x * r.x + r.y * r.y); // if ((t <= u && (t > 1 || u < 0)) || (u < t && (u > 1 || t < 0))) // return false; // else // return true; // } else // return false; // } else if (0 <= t && t <= 1 && 0 <= u && u <= 1) // return true; // else // return false; //} double dist(Point q0,Point q1,Point p) { Point r = q1 - q0, p0 = p - q0, proj; double l2 = r.x * r.x + r.y * r.y, t; if (l2 == 0) return sqrt(p0.x*p0.x+p0.y*p0.y); t = (p0.x * r.x + p0.y * r.y) / l2; if (t < 0) t = 0; if (t > 1) t = 1; proj = q0 + r * t - p; return sqrt(proj.x * proj.x + proj.y * proj.y); } int main() { Point p0, p; int32_t r, nPoints; vector polygon; // input cin >> p0.x >> p0.y >> r >> nPoints; REPI(i,0,nPoints) { cin >> p.x >> p.y; polygon.push_back(p); } // points should be different REPI(i,0,nPoints-1) if (polygon[i] == polygon[i+1]) { cout << "Points are same" << endl; return 0; } // 3 adjacent vertices should not be collinear and should be convex REPI(i,0,nPoints) { if ((polygon[(i+1)%nPoints]-polygon[i]) * (polygon[(i+2)%nPoints]-polygon[i]) <= 0) { cout << "Adjacent collinear segments or not convex" << endl; return 1; } } // non-adjacent segments should not intersect anywhere, not even at endpoints // note: this is probably redundant since the polygon must be convex // REPI(i,0,nPoints) // REPI(j,0,nPoints-3) // if (intersect(polygon[i],polygon[(i+1)%nPoints], // polygon[(i+j+2)%nPoints],polygon[(i+j+3)%nPoints])) { // cout << "Not simple polygon" << endl; // return 2; // } // distance from center to each segment must be > r REPI(i,0,nPoints) if (dist(polygon[i],polygon[(i+1)%nPoints],p0) <= r) { cout << "Polygon not outside circle" << endl; return 3; } return 42; }