জ্যামিতি

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 22;
const double eps = 1e-8;

struct pt{
    double x, y;
    pt(){}
    pt(double a, double b){
        x = a; y = b;
    }
    void get(){
        scanf ("%lf %lf", &x, &y);
    }
};

struct line{
    double a, b, c;
    line (){}
    line (pt p, pt q){
        a = p.y - q.y;
        b = q.x - p.x;
        c = -a * p.x - b * p.y;
    }
    double side (const pt &p){
        return a * p.x + b * p.y + c;
    }
    bool parallel (const line &other){
        return fabs (a * other.b - b * other.a) < eps;
    }
    pt intersect (const line &other){
        double d = a * other.b - b * other.a;
        double dx = b * other.c - c * other.b;
        double dy = c * other.a - a * other.c;
        return pt (dx / d, dy / d);
    }
};

pt a[maxn], b[maxn];

int main (){
//    filein;
    int n;
    while (~scanf ("%d", &n) and n){
        for (int i = 0; i < n; i++){
            a[i].get();
            b[i] = pt (a[i].x, a[i].y - 1.0);
        }
        bool through = false;
        double maxi = a[0].x;
        for (int i = 0; i < n and !through; i++){
            for (int j = 0; j < n; j++){
                if (i == j) continue;
                line L (a[i], b[j]);
                int k;
                for (k = 0; k < n; k++){
                    if (L.side (a[k]) * L.side (b[k]) > eps)
                        break;
                }
                if (k == n){
                    through = true;
                    break;
                }
                if (k){
                    pt out;
                    if (L.side (a[k]) * L.side (a[k - 1]) < eps){
                        out = L.intersect (line (a[k], a[k - 1]));
                        maxi = max (maxi, out.x);
                    }
                    if (L.side (b[k]) * L.side (b[k - 1]) < eps){
                        out = L.intersect (line (b[k], b[k - 1]));
                        maxi = max (maxi, out.x);
                    }
                }
            }
        }
        if (through) puts ("Through all the pipe.");
        else printf ("%.2f\n", maxi);
    }
    return 0;
}

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 20000;
const double eps = 1e-8;

int dcmp (double a){
    if (fabs (a) < eps) return 0;
    return (a > eps ? 1 : -1);
}

struct pt{
    double x, y;
    pt (){}
    pt (double a, double b){
        x = a; y = b;
    }
    void get (){
        scanf ("%lf %lf", &x, &y);
    }
};

struct line{
    double a, b, c;
    line(){}
    line(pt p, pt q){
        a = p.y - q.y;
        b = q.x - p.x;
        c = -a * p.x - b * p.y;
    }
    double plug (pt p){
        return a * p.x + b * p.y + c;
    }
    pt intersection (line other){
        double d = a * other.b - b * other.a;
        double dx = b * other.c - c * other.b;
        double dy = c * other.a - a * other.c;
        return pt (dx / d, dy / d);
    }
};

pt can[maxn];
line lines[maxn];

int main (){
//    filein;
    can[0] = pt (0, 100);
    can[1] = pt (100, 100);
    can[2] = pt (100, 0);
    can[3] = pt (0, 0);
    int t;
    scanf ("%d", &t);
    bool f = true;
    while (t--){
        if (!f) puts ("");
        f = false;
        int n;
        scanf ("%d", &n);
        int cnt = 4, l = 0;
        for (int i = 0; i < n; i++){
            pt a, b;
            a.get(); b.get();
            lines[l++] = line (a, b);
            can[cnt++] = a;
            can[cnt++] = b;
        }
        pt x;
        x.get();
        int ans = 10000000;
        for (int i = 0; i < cnt; i++){
            int num = 0;
            for (int j = 0; j < l; j++){
                if (dcmp (lines[j].plug (x) * lines[j].plug (can[i])) == -1)
                    num++;
            }
            ans = min (ans, num);
        }
        printf ("Number of doors = %d\n", ans + 1);
    }
    return 0;
}

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;
typedef long long ll;

const double pi = acos (-1.0);

typedef double T;
struct pt{
    T x, y;
    pt (){}
    pt (T _x, T _y){
        x = _x; y = _y;
    }
    pt operator + (pt p){
        return pt (x + p.x, y + p.y);
    }
    pt operator - (pt p){
        return pt (x - p.x, y - p.y);
    }
    pt operator * (T d){
        return pt (x * d, y * d);
    }
    pt operator / (T d){
        return pt (x / d, y / d);
    }
};

T sq (pt p){
    return p.x * p.x + p.y * p.y;
}

T cross (pt v, pt w){
    return v.x * w.y - v.y * w.x;
}

T orient (pt a, pt b, pt c){
    return cross (b - a, c - a);
}

vector <pt> v;

int main(){
//    freopen ("in.txt", "r", stdin);
    pt t;
    double r;
    int X, Y;
    while (scanf("%d %d %lf", &X, &Y, &r)){
        if (r < 0.0) break;
        t.x = X;
        t.y = Y;
        v.clear();
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++){
            scanf("%d %d", &X, &Y);
            v.push_back (pt (X, Y));
        }
        int maxi = 0;
        for (int i = 0, sz = v.size(); i < sz; i++){
            pt a = v[i];
            int cnt = 0;
            if (sq (t - a) <= r * r) cnt = 1;
            for (int j = 0; j < sz; j++){
                if (j == i) continue;
                if (orient (t, a, v[j]) >= 0 and (sq (t - v[j])) <= r * r) cnt++;
            }
            maxi = max (maxi, cnt);
        }
        printf ("%d\n", maxi);
    }
    return 0;
}

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 2002;

struct pt{
    int x, y;
    pt (){}
    pt (int a, int b){
        x = a; y = b;
    }
    pt operator - (const pt &a){
        return pt (x - a.x, y - a.y);
    }
    bool operator < (const pt &a) const {
        if (x == a.x) return (y < a.y);
        return x < a.x;
    }
    void get(){
        scanf ("%d %d", &x, &y);
    }
};

int cross (pt a, pt b){
    return a.x * b.y - a.y * b.x;
}

int orient (pt a, pt b, pt c){
    return cross (b - a, c - a);
}

double dist (pt a, pt b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt (dx * dx + dy * dy);
}

pt a[maxn], H[maxn];

int main (){
//    filein;
    int n, r;
    scanf ("%d %d", &n, &r);
    for (int i = 0; i < n; i++){
        a[i].get();
    }
    int st = 0;
    sort (a, a + n);
    for (int i = 0; i < n; i++){
        while (st >= 2 and orient (H[st - 2], H[st - 1], a[i]) < 0)
            st--;
        H[st++] = a[i];
    }
    int taken = st - 1;
    for (int i = n - 2; i >= 0; i--){
        while (st >= taken + 2 and orient (H[st - 2], H[st - 1], a[i]) < 0)
            st--;
        H[st++] = a[i];
    }
    double ans = 2.0 * acos (-1.0) * r;
    for (int i = 0; i < st - 1; i++)
        ans += dist (H[i], H[i + 1]);
    printf ("%d\n", (int) round (ans));
    return 0;
}

#include <iostream>
#include <cstdio>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 102;

struct pt{
    int x, y;
    pt(){}
    pt(int a, int b){
        x = a; y = b;
    }
    pt operator - (pt other){
        return pt (x - other.x, y - other.y);
    }
    void get (){
        scanf ("%d %d", &x, &y);
    }
};

int dot (pt a, pt b){
    return a.x * b.x + a.y * b.y;
}

int cross (pt a, pt b){
    return a.x * b.y - a.y * b.x;
}

int orient (pt a, pt b, pt c){
    return cross (b - a, c - a);
}

bool indisk (pt a, pt b, pt p){
    return dot (a - p, b - p) <= 0;
}

bool onsegment (pt a, pt b, pt p){
    return orient (a, b, p) == 0 and indisk (a, b, p);
}

pair <pt, pt> a[maxn];

bool ok (pt w, pt x, pt y, pt z){
    if (onsegment (w, x, y)) return true;
    if (onsegment (w, x, z)) return true;
    if (onsegment (y, z, w)) return true;
    if (onsegment (y, z, x)) return true;
    int d1 = orient (w, x, y),
        d2 = orient (w, x, z),
        d3 = orient (y, z, w),
        d4 = orient (y, z, x);
    return (d1 * d2 < 0 and d3 * d4 < 0);
}

int parent[maxn];

int findparent (int a){
    if (parent[a] == a) return a;
    return parent[a] = findparent (parent[a]);
}

int main (){
//    filein;
    int n;
    while (~scanf ("%d", &n) and n){
        for (int i = 1; i <= n; i++){
            a[i].first.get();
            a[i].second.get();
            parent[i] = i;
        }
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if (i == j) continue;
                if (ok (a[i].first, a[i].second, a[j].first, a[j].second)){
                    int pa = findparent (i);
                    int pb = findparent (j);
                    if (pa != pb){
                        parent[pa] = pb;
                    }
                }
            }
        }
        int u, v;
        while (~scanf ("%d %d", &u, &v)){
            if (!u and !v) break;
            if (findparent (u) == findparent (v))
                puts ("CONNECTED");
            else puts ("NOT CONNECTED");
        }
    }
    return 0;
}

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <cassert>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

typedef int T;
struct pt{
    T x, y;
    pt (){}
    pt (T _x, T _y){
        x = _x; y = _y;
    }
};

T sq (pt p){
    return p.x * p.x + p.y * p.y;
}

double abs (pt p){
    return sqrt (sq (p));
}

T cross (pt v, pt w){
    return v.x * w.y - v.y * w.x;
}

double areaPolygon (const vector <pt>& p){
    double area = 0.0;
    for (int i = 0, n = p.size(); i < n; i++){
        area += cross (p[i], p[(i + 1) % n]);
    }
    return fabs (area) / 2.0;
}

int boundaryPoints (pt a, pt b){
    //requires int representation
    return __gcd (abs (a.x - b.x), abs (a.y - b.y)) + 1;
}

vector <pt> v;

int main (){
//    freopen ("in.txt", "r", stdin);
    int test;
    scanf("%d", &test);
    for (int _z = 0; _z < test; _z++){
        v.clear();
        int n;
        scanf("%d", &n);
        pt a (0, 0);
        v.push_back (a);
        for (int i = 0; i < n - 1; i++){
            int x, y;
            scanf("%d %d", &x, &y);
            a.x += x; a.y += y;
            v.push_back (a);
        }
        scanf("%d %d", &a.x, &a.y);
        int I, B = 0;
        double A;
        for (int i = 0; i < n; i++){
            B += (boundaryPoints(v[i], v[(i + 1) % n]));
        }
        B -= n;
        A = areaPolygon(v);
        I = A - (B / 2) + 1;
        printf("Scenario #%d:\n", _z + 1);
        printf("%d %d %.1f\n\n", I, B, A);
    }
}

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 102;
const double eps = 1e-8 ;

struct pt{
    double x, y;
    pt (){}
    pt (double _x, double _y){
        x = _x; y = _y;
    }
    pt operator - (pt a){
        return pt (x - a.x, y - a.y);
    }
    void get (){
        scanf ("%lf %lf", &x, &y);
    }
};

double cross (pt a, pt b){
    return a.x * b.y - a.y * b.x;
}

int orient (pt a, pt b, pt c){
    double d = cross (b - a, c - a);
    if (fabs (d) < eps) return 0;
    if (d < 0) return -1;
    return 1;
}

struct line{
    double a, b, c;
    line (){}
    line (pt p, pt q){
        a = p.y - q.y;
        b = q.x - p.x;
        c = -a * p.x - b * p.y;
    }
};

bool areParallel (line p, line q){
    return (fabs (p.a * q.b - q.a * p.b) < eps);
}

bool areSame (line p, line q){
    return areParallel(p, q) and (fabs (p.b * q.c - q.b * p.c) < eps) and (fabs (p.a * q.c - q.a * p.c) < eps);
}

bool intersect (line p, line q, pt& out){
    if (areParallel(p, q)) return false;
    double d = p.a * q.b - q.a * p.b;
    out.x = (p.b * q.c - p.c * q.b) / d;
    out.y = (q.a * p.c - p.a * q.c) / d;
//    cerr << out.x << " " << out.y << endl;
    return true;
}

int main(){
//    filein;
//    fileout;
    int t;
    scanf ("%d", &t);
    puts ("INTERSECTING LINES OUTPUT");
    while (t--){
        pt a, b, c, d;
        a.get(); b.get(); c.get(); d.get();
        line l1 (a, b);
        line l2 (c, d);
        if (areSame (l1, l2)) puts ("LINE");
        else if (areParallel(l1, l2)) puts ("NONE");
        else{
            pt out;
            intersect (l1, l2, out);
            printf ("POINT %.2f %.2f\n", out.x + eps, out.y + eps);
        }
    }
    puts ("END OF OUTPUT");
    return 0;
}

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;
typedef long long ll;

const double pi = acos (-1.0);

typedef int T;
struct pt{
    T x, y;
    pt (){}
    pt (T _x, T _y){
        x = _x; y = _y;
    }
    pt operator + (pt p){
        return pt (x + p.x, y + p.y);
    }
    pt operator - (pt p){
        return pt (x - p.x, y - p.y);
    }
    pt operator / (T d){
        return pt (x / d, y / d);
    }

};

T dot (pt v, pt w){
    return v.x * w.x + v.y * w.y;
}

T cross (pt v, pt w){
    return v.x * w.y - v.y * w.x;
}

T orient (pt a, pt b, pt c){
    return cross (b - a, c - a);
}

bool inDisk (pt a, pt b, pt p){
    return dot (a - p, b - p) <= 0;
}

bool onSegment (pt a, pt b, pt p){
    return orient (a, b, p) == 0 and inDisk (a, b, p);
}

bool properInter (pt a, pt b, pt c, pt d, pt& i){
    int oa = orient (c, d, a),
           ob = orient (c, d, b),
           oc = orient (a, b, c),
           od = orient (a, b, d);

    if (oa * ob < 0 and oc * od < 0){
        i = (a * ob - b * oa) / (ob - oa);
        return true;
    }
    return false;
}

bool inters (pt a, pt b, pt c, pt d){
    pt out;
    if (properInter (a, b, c, d, out)) return true;
    if (onSegment (c, d, a)) return true;
    if (onSegment (c, d, b)) return true;
    if (onSegment (a, b, c)) return true;
    if (onSegment (a, b, d)) return true;
    return false;
}

bool pointInPolygon(const vector<pt> &p, pt q){
    bool c = false;
    for (int i = 0; i < p.size(); i++){
        int j = (i + 1) % p.size();
        if ((p[i].y <= q.y and q.y < p[j].y or p[j].y <= q.y and q.y < p[i].y) and
            q.x < p[i].x + (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y))
                c = !c;
    }
    return c;
}

vector <pt> v;

int main (){
//    freopen ("in.txt", "r", stdin);
    int test;
    scanf("%d", &test);
    for (int _z = 0; _z < test; _z++){
        pt a, b;
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &a.x, &a.y, &b.x, &b.y);
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        v.clear();
        v.push_back (pt (x1, y1));
        v.push_back (pt (x2, y1));
        v.push_back (pt (x2, y2));
        v.push_back (pt (x1, y2));

        bool ret = inters (v[0], v[1], a, b) | inters (v[1], v[2], a, b) | inters (v[2], v[3], a, b) | inters (v[3], v[0], a, b);
        if (pointInPolygon(v, a) and pointInPolygon(v, b)) ret = true;
        if (ret) puts ("T");
        else puts ("F");
    }
    return 0;
}

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>


#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 55000;

struct pt{
    int x, y;
    pt(){}
    pt(int a, int b){
        x = a, y = b;
    }
    void get (){
        scanf ("%d %d", &x, &y);
    }
    pt operator - (const pt &other) {
        return pt (x - other.x, y - other.y);
    }
    bool operator < (const pt &other) const {
        if (x == other.x) return (y < other.y);
        return (x < other.x);
    }
};

int cross (pt a, pt b){
    return a.x * b.y - a.y * b.x;
}

int orient (pt a, pt b, pt c){
    return (cross (b - a, c - a));
}

int dist (pt a, pt b){
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return dx * dx + dy * dy;
}

pt a[maxn], hull[maxn];

int main (){
//    filein;
    int n;
    scanf ("%d", &n);
    for (int i = 0; i < n; i++)
        a[i].get();

    sort (a, a + n);
    int st = 0;
    for (int i = 0; i < n; i++){
        while (st >= 2 and orient (hull[st - 2], hull[st - 1], a[i]) <= 0)
            st--;
        hull[st++] = a[i];
    }
    int taken = st - 1;
    for (int i = n - 2; i >= 0; i--){
        while (st >= taken + 2 and orient (hull[st - 2], hull[st - 1], a[i]) <= 0)
            st--;
        hull[st++] = a[i];
    }

    int maxi = 0;

    for (int i = 0; i < st - 1; i++){
        for (int j = i + 1; j < st - 1; j++){
            maxi = max (maxi, dist (hull[i], hull[j]));
        }
    }

    printf ("%d\n", maxi);
    return 0;
}

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const double pi = 3.141592653589793;

struct pt{
    double x, y;
    pt(){}
    pt (double a, double b){
        x = a, y = b;
    }
    pt operator + (const pt &p){
        return pt (x + p.x, y + p.y);
    }
    pt operator / (const double d){
        return pt (x / d, y / d);
    }
};

double dist (pt a, pt b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt (dx * dx + dy * dy);
}

struct line{
    double a, b, c;
    line(){}
    line (pt p, pt q){
        a = p.y - q.y;
        b = q.x - p.x;
        c = -a * p.x - b * p.y;
    }
    line perpendicular (pt p){
        line l;
        l.a = b;
        l.b = -a;
        l.c = -l.a * p.x - l.b * p.y;
        return l;
    }
    pt intersect (line other){
        double d = a * other.b - b * other.a;
        double dx = b * other.c - c * other.b;
        double dy = c * other.a - a * other.c;
        return pt (dx / d, dy / d);
    }
};

int main (){
//    filein;
    pt a, b, c;
    while (cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y){
        line l1 (line (a, b).perpendicular((a + b) / 2));
        line l2 (line (b, c).perpendicular((b + c) / 2));
        pt mid = l1.intersect(l2);
        double r = dist (mid, a);
        printf ("%.2f\n", 2.0 * pi * r);
    }
    return 0;
}

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 1105;
const double eps = 1e-8;

int a[maxn], b[maxn];
double d[maxn * maxn];

int main (){
//    filein;
    int n;
    while (~scanf ("%d", &n)){
        for (int i = 0; i < n; i++){
            scanf ("%d %d", &a[i], &b[i]);
        }
        int inv;
        int cnt, maxi = 0;
        for (int i = 0; i < n; i++){
            inv = cnt = 0;
            for (int j = i + 1; j < n; j++){
                int dx = a[i] - a[j];
                int dy = b[i] - b[j];
                if (dx == 0) inv++;
                else d[cnt++] = (1.0 * dy / dx);
            }
            sort (d, d + cnt);
            int streak = 1;
            double prev = d[0];
            for (int i = 1; i < cnt; i++){
                if (fabs (d[i] - prev) < eps){
                    streak++;
                }
                else{
                    maxi = max (maxi, streak);
                    streak = 1;
                }
                prev = d[i];
            }
            maxi = max (maxi, streak);
            maxi = max (maxi, inv);
        }
        printf ("%d\n", maxi + 1);
    }
    return 0;
}

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 102;
const double eps = 1e-6 ;

struct pt{
    double x, y;
    pt (){}
    pt (double _x, double _y){
        x = _x; y = _y;
    }
    pt operator - (pt a){
        return pt (x - a.x, y - a.y);
    }
    void get (){
        scanf ("%lf %lf", &x, &y);
    }
};

double cross (pt a, pt b){
    return a.x * b.y - a.y * b.x;
}

int orient (pt a, pt b, pt c){
    double d = cross (b - a, c - a);
    if (fabs (d) < eps) return 0;
    if (d < 0) return -1;
    return 1;
}

struct line{
    double a, b, c;
    line (){}
    line (pt p, pt q){
        a = p.y - q.y;
        b = q.x - p.x;
        c = -a * p.x - b * p.y;
    }
};

bool areParallel (line p, line q){
    return (fabs (p.a * q.b - q.a * p.b) < eps);
}

bool intersect (line p, line q, pt& out){
    if (areParallel(p, q)) return false;
    double d = p.a * q.b - q.a * p.b;
    out.x = (p.b * q.c - p.c * q.b) / d;
    out.y = (q.a * p.c - p.a * q.c) / d;
//    cerr << out.x << " " << out.y << endl;
    return true;
}

pt a[maxn];

bool ok (pt out, int n){
    bool pos = false, neg = false;
    for (int i = 0; i < n; i++){
        int d = orient (a[i], a[(i + 1) % n], out);
        if (d == 1) pos = true;
        else if (d == -1) neg = true;
    }
    if (pos and neg) return false;
    return true;
}

int main (){
//    filein;
    int n;
    while (~scanf ("%d", &n) and n){
        for (int i = 0; i < n; i++) a[i].get();
        bool ans = false;
        for (int i = 0; i < n and !ans; i++){
            for (int j = i + 1; j < n; j++){
                pt out;
                if (intersect (line (a[i], a[(i + 1) % n]), line (a[j], a[(j + 1) % n]), out)){
                    if (ok (out, n)){
                        ans = true;
                        break;
                    }
                }
            }
        }
        if (ans) puts ("1");
        else puts ("0");
    }
    return 0;
}

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 102;
const double eps = 1e-6 ;

struct pt{
    double x, y;
    pt (){}
    pt (double _x, double _y){
        x = _x; y = _y;
    }
    pt operator - (pt a){
        return pt (x - a.x, y - a.y);
    }
    void get (){
        scanf ("%lf %lf", &x, &y);
    }
};

double cross (pt a, pt b){
    return a.x * b.y - a.y * b.x;
}

int orient (pt a, pt b, pt c){
    double d = cross (b - a, c - a);
    if (fabs (d) < eps) return 0;
    if (d < 0) return -1;
    return 1;
}

struct line{
    double a, b, c;
    line (){}
    line (pt p, pt q){
        a = p.y - q.y;
        b = q.x - p.x;
        c = -a * p.x - b * p.y;
    }
};

bool areParallel (line p, line q){
    return (fabs (p.a * q.b - q.a * p.b) < eps);
}

bool intersect (line p, line q, pt& out){
    if (areParallel(p, q)) return false;
    double d = p.a * q.b - q.a * p.b;
    out.x = (p.b * q.c - p.c * q.b) / d;
    out.y = (q.a * p.c - p.a * q.c) / d;
//    cerr << out.x << " " << out.y << endl;
    return true;
}

pt a[maxn];
pair <pt, pt> lines[maxn];
pt points[maxn * maxn];

int main (){
//    filein;
    int t;
    scanf ("%d", &t);
    while (t--){
        int n;
        scanf ("%d", &n);
        for (int i = 0; i < n; i++) a[i].get();
        for (int i = 0; i < n; i++){
            lines[i] = make_pair (a[i], a[(i + 1) % n]);
        }
        int cnt = 0;
        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                pt out;
                if (intersect (line (lines[i].first, lines[i].second), line (lines[j].first, lines[j].second), out)){
                    points[cnt++] = out;
                }
            }
        }
        bool ans = false;
        for (int c = 0; c < cnt; c++){
            bool pos = false, neg = false;
            for (int i = 0; i < n; i++){
                int o = orient (a[i], a[(i + 1) % n], points[c]);
                if (o == 1) pos = true;
                else if (o == -1) neg = true;
            }
            if ((!pos and neg) or (!neg and pos)){
                ans = true;
                break;
            }
        }
        if (ans) puts ("YES");
        else puts ("NO");
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 150;
const long double eps = 1e-4;

struct fr{
    ll a, b;
    fr(){}
    fr(ll x){
        a = x; b = 1;
    }
    fr (ll x, ll y){
        a = x; b = y;
    }
    fr operator - (){
        return fr (-a, b);
    }
    fr operator - (fr other){
        ll up = a * other.b - b * other.a;
        ll down = b * other.b;
        ll g = __gcd (up, down);
        return fr (up / g, down / g);
    }
    fr operator * (fr other){
        ll up = a * other.a;
        ll down = b * other.b;
        ll g = __gcd (up, down);
        return fr (up / g, down / g);
    }
    fr operator / (fr other){
        ll g = __gcd (a, other.a);
        a /= g; other.a /= g;
        g = __gcd (b, other.b);
        b /= g; other.b /= g;
        a *= other.a; b *= other.a;
        g = __gcd (a, b);
        return fr (a / g, b / g);
    }
    bool operator == (fr other){
        if (a < 0) a = -a, b = -b;
        if (other.a < 0) other.a = -other.a, other.b = -other.b;
        return (a == other.a and b == other.b);
    }
};

struct pt{
    fr x, y;
    pt(){}
    pt(fr a, fr b){
        x = a; y = b;
    }
    void get (){
        ll a, b;
        scanf ("%lld %lld", &a, &b);
        x.a = a; x.b = 1;
        y.a = b; y.b = 1;
    }
    pt operator / (fr d){
        return pt (x / d, y / d);
    }
    bool operator == (pt a){
        return (a.x == x and a.y == y);
    }
};

struct line{
    fr a, b, c;
    line (pt p, pt q){
        a = p.y - q.y;
        b = q.x - p.x;
        c = -a * p.x - b * p.y;
    }
    bool parallel (line other){
        return a * other.b == b * other.a;
    }
    pt intersect (line other){
        fr d = a * other.b - b * other.a;
        fr dx = b * other.c - c * other.b;
        fr dy = c * other.a - a * other.c;
        return pt (dx / d, dy / d);
    }
};

pt arr[maxn];

int main (){
//    filein;
    int n;
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++)
        arr[i].get();
    int m;
    scanf ("%d", &m);
    int ans = 0;
    for (int i = 1; i <= m; i++){
        int a, b, c, d;
        scanf ("%d %d %d %d", &a, &b, &c, &d);
        if (ans > 0) continue;
        pt out = line (arr[a], arr[b]).intersect(line (arr[c], arr[d]));
        if (out == pt (0, 0)) ans = i;
        arr[n + i] = out;
    }
    printf ("%d\n", ans);
    return 0;
}

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
#define dbg(x) cerr << #x << ": " << x << endl

using namespace std;
typedef long long ll;

const int maxn = 1005;
const double pi = 3.141;
const double eps = 1e-8;

struct pt{
    double x, y;
    void get(){
        scanf ("%lf %lf", &x, &y);
    }
};

double dist (pt a, pt b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt (dx * dx + dy * dy);
}

pt a[maxn];
double d1[maxn], d2[maxn];

int main (){
//    filein;
    int n, cs = 1;
    while (~scanf ("%d", &n) and n){
        pt c1, c2;
        double area;
        c1.get();
        c2.get();
        scanf ("%lf", &area);
        for (int i = 0; i < n; i++){
            a[i].get();
            d1[i] = dist (c1, a[i]);
            d2[i] = dist (c2, a[i]);
        }

        int maxi = 0;

        for (int i = 0; i < n; i++){
            double d = d1[i];
            if (pi * d * d > area) continue;
            double now_area = area - pi * d * d;
            double r = sqrt (now_area / pi);
            int cnt = 0;
            for (int j = 0; j < n; j++)
                if (d1[j] < d + eps or d2[j] < r + eps)
                    cnt++;
            maxi = max (maxi, cnt);
        }

        for (int i = 0; i < n; i++){
            double d = d2[i];
            if (pi * d * d > area) continue;
            double now_area = area - pi * d * d;
            double r = sqrt (now_area / pi);
            int cnt = 0;
            for (int j = 0; j < n; j++)
                if (d2[j] < d + eps or d1[j] < r + eps)
                    cnt++;
            maxi = max (maxi, cnt);
        }
        printf ("%d. %d\n", cs++, n - maxi);
    }
    return 0;
}