计算几何

……我好菜啊……

AOJ CGL_1_A

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
struct Point
{
    double x, y;
    Point(int a, int b){x = a, y = b;}
    Point(double a = .0, double b = .0){x = a, y = b;}
    Point operator+(Point q){return Point(x + q.x, y + q.y);}
    Point operator-(Point q){return Point(x - q.x, y - q.y);}
    Point operator*(double a){return Point(x * a, y * a);}
} P1, P2, P;
struct Segment
{
    Point a, b;
    Segment(Point x, Point y){a = x, b = y;}
};
#define sqr(x) ((x) * (x))
inline double dot(Point x, Point y){return x.x * y.x + x.y * y.y;}
inline double norm(Point s){return dot(s, s);}
int main()
{
    int x1, y1, x2, y2, x, y; read(x1, y1), read(x2, y2); P1 = Point(x1, y1), P2 = Point(x2, y2);
    Segment S = Segment(P1, P2);
    int q; read(q);
    while(q--)
    {
        read(x, y); P = Point(x, y);
        double r = dot(P - S.a, S.b - S.a) / norm(S.b - S.a);
        Point x = S.a + (S.b - S.a) * r;
        printf("%.9lf %.9lf\n", x.x, x.y);
    }
    return 0;
}

AOJ CGL_1_C

ccw.

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
struct Point
{
    double x, y;
    Point(int a, int b){x = a, y = b;}
    Point(double a = .0, double b = .0){x = a, y = b;}
    Point operator+(const Point& r){return Point(x + r.x, y + r.y);}
    Point operator-(const Point& r){return Point(x - r.x, y - r.y);}
    Point operator*(double r){return Point(x * r, y * r);}
    double operator*(const Point& r){return x * r.y - y * r.x;}
};
typedef Point Vector;
double dot(Vector l, Vector r){return l.x * r.x + l.y * r.y;}
double norm(Vector l){return dot(l, l);}
char* ccw(Point x, Point y, Point z)
{
    double cross = (y - x) * (z - x);
    if(cross > 0) return "COUNTER_CLOCKWISE";
    if(cross < 0) return "CLOCKWISE";
    if(dot(y - x, z - x) < 0) return "ONLINE_BACK";
    if(norm(y - x) < norm(z - x)) return "ONLINE_FRONT";
    return "ON_SEGMENT";
}
int main()
{
    int x0, y0, x1, y1, x, y; read(x0, y0), read(x1, y1);
    int q; read(q);
    while(q--)
    {
        read(x, y);
        puts(ccw(Point(x0, y0), Point(x1, y1), Point(x, y)));
    }
    return 0;
}

AOJ CGL_2_C

求线段交点。式子很妙。

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
struct Point
{
    double x, y;
    Point(int a, int b){x = a, y = b;}
    Point(double a = .0, double b = .0){x = a, y = b;}
    Point operator+(const Point& r){return Point(x + r.x, y + r.y);}
    Point operator-(const Point& r){return Point(x - r.x, y - r.y);}
    Point operator*(double r){return Point(x * r, y * r);}
    double operator*(const Point& r){return x * r.y - y * r.x;}
};
typedef Point Vector;
inline double norm(Vector l){return l.x * l.x + l.y * l.y;}
inline double abs(Vector l){return sqrt(norm(l));}
inline Vector Norm(Vector a){return a * (1 / abs(a));}
inline Point CrossPoint(Point x, Vector u, Point y, Vector v)
{Vector w = x - y;return x + u * ((v * w) / (u * v));}
int main()
{
    int q, x0, y0, x1, y1, x2, y2, x3, y3; read(q);
    while(q--)
    {
        read(x0, y0), read(x1, y1), read(x2, y2), read(x3, y3);
        Point ret = CrossPoint(Point(x0, y0), (Point(x1, y1) - Point(x0, y0)), Point(x2, y2), (Point(x3, y3) - Point(x2, y2)));
        printf("%.10lf %.10lf\n", ret.x, ret.y);
    }
    return 0;
}

AOJ CGL_3_C

点包含。统计过该点平行于x轴的直线过边界的交点数量的奇偶即可。

Code

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const double eps = 1e-10;
const int maxn = 1e3;
struct Point
{
    double x, y;
    Point(int a, int b){x = a, y = b;}
    Point(double a = .0, double b = .0){x = a, y = b;}
    Point operator+(const Point& r){return Point(x + r.x, y + r.y);}
    Point operator-(const Point& r){return Point(x - r.x, y - r.y);}
    Point operator*(double r){return Point(r * x, r * y);}
    double operator*(const Point& r){return x * r.y - y * r.x;}
} g[maxn];
int n; 
typedef Point Vector;
inline double dot(Vector l, Vector r){return l.x * r.x + l.y * r.y;}
int contains(Point p)
{
    bool x = false;
    for(int i = 0; i < n; ++i)
    {
        Vector a = g[i] - p, b = g[(i + 1) % n] - p;
        double cross = a * b;
        if(abs(cross) < eps && dot(a, b) < eps) return 1;
        if(a.y > b.y) swap(a, b), cross = a * b;
        if(a.y < eps && eps < b.y && cross > eps) x = !x;
    }
    return x ? 2 : 0;
}
int main()
{
    read(n);
    for(int i = 0, x, y; i < n; ++i) read(x, y), g[i] = Point(x, y);
    int q; read(q);
    while(q--)
    {
        int x, y; read(x, y);
        printf("%d\n", contains(Point(x, y)));
    }
    return 0;
}

AOJ DSL_2_C

平面范围查询。k-d tree 基本应用。

AOJ CGL_4_A

求凸包。输出有特殊格式。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e5 + 5;
struct P
{
    int x, y;
    P(int a = 0, int b = 0) {x = a, y = b;}
    //P(double a = .0, double b = .0){x = a, y = b;}
    P operator-(const P& r){return P(r.x - x, r.y - y);}
    int operator*(const P& r){return x * r.y - y * r.x;}
    bool operator<(const P& r)const{return x == r.x ? y < r.y : x < r.x;}
} p[maxn];
int s[maxn << 1], t;
int main()
{
    int n; read(n);
    for(int i = 1; i <= n; ++i) read(p[i].x, p[i].y);
    sort(p + 1, p + n + 1);
    // if(n == 3)
    // {
    //     printf("%d\n%d %d\n%d %d\n%d %d\n", 3, p[1].x, p[1].y, p[2].x, p[2].y, p[3].x, p[3].y);
    //     return 0;
    // }
    s[0] = 1, s[1] = 2, t = 2;
    for(int i = 3; i <= n; ++i)
    {
        int ret;
        while(t > 1 && (ret = (p[i] - p[s[t - 2]]) * (p[s[t - 1]] - p[s[t - 2]])) > 0) --t;
        s[t++] = i;
    }
    int tt = t - 1;
    s[t++] = n - 1; //fa2[n] = n + 1;
    for(int i = n - 2; i; --i)
    {
        while(t > tt && (p[i] - p[s[t - 2]]) * (p[s[t - 1]] - p[s[t - 2]]) > 0) --t; 
        s[t++] = i;
    }
    --t;
    printf("%d\n", t);
    int num = 0;
    for(int i = 0; i < t; ++i) if(p[s[i]].y < p[s[num]].y) num = i;
    for(int i = num; i < t; ++i) printf("%d %d\n", p[s[i]].x, p[s[i]].y);
    for(int i = 0; i < num; ++i) printf("%d %d\n", p[s[i]].x, p[s[i]].y);
    return 0;
}

AOJ CGL_5_A

平面最小点对。证明很妙。有空补。

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e5 + 5;
const double eps = 1e-7, INF = 100000000000000000000;
struct P{double x, y; bool operator<(const P& r)const{return abs(x - r.x) < eps ? y < r.y : x < r.x;}} p[maxn], temp[maxn];
inline double dis(P a, P b){return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));}
int n;
inline bool cmp(P a, P b){return a.y < b.y;}
double dc(int L = 1, int R = n)
{
    if(L == R) return INF;
    if(L + 1 == R) return dis(p[L], p[R]);
    int M = (L + R) >> 1;
    double ans = min(dc(L, M), dc(M + 1, R));
    int k = 0;
    for(int i = L; i <= R; ++i) if(abs(p[M].x - p[i].x) <= ans)
        temp[k++] = p[i];
    sort(temp, temp + k, cmp);
    for(int i = 0; i < k; ++i) for(int j = i + 1; j < k && temp[j].y - temp[i].y <= ans; ++j)
        ans = min(ans, dis(temp[i], temp[j]));
    return ans;
}
int main()
{
    read(n);
    for(int i = 1; i <= n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);
    sort(p + 1, p + n + 1);
    printf("%.7lf\n", dc());
    return 0;
}

Vijos 1012

同上。

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e5 + 5;
const double eps = 1e-7, INF = 100000000000000000000;
struct P{double x, y; bool operator<(const P& r)const{return abs(x - r.x) < eps ? y < r.y : x < r.x;}} p[maxn], temp[maxn];
inline double dis(P a, P b){return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));}
int n;
inline bool cmp(P a, P b){return a.y < b.y;}
double dc(int L = 1, int R = n)
{
    if(L == R) return INF;
    if(L + 1 == R) return dis(p[L], p[R]);
    int M = (L + R) >> 1;
    double ans = min(dc(L, M), dc(M + 1, R));
    int k = 0;
    for(int i = L; i <= R; ++i) if(abs(p[M].x - p[i].x) <= ans)
        temp[k++] = p[i];
    sort(temp, temp + k, cmp);
    for(int i = 0; i < k; ++i) for(int j = i + 1; j < k && temp[j].y - temp[i].y <= ans; ++j)
        ans = min(ans, dis(temp[i], temp[j]));
    return ans;
}
int main()
{
    read(n);
    for(int i = 1; i <= n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);
    sort(p + 1, p + n + 1);
    printf("%.3lf\n", dc());
    return 0;
}

POJ 3714

平面最小点对，要求两点属于不同集合。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e5 + 5, INF = 0x7fffffff;
struct P{double x, y; int t; 
    bool operator<(const P&r)const{return x == r.x ? (y == r.y ? t < r.t : y < r.y) : x < r.x;}
    bool operator==(const P& r)const{return x == r.x && y == r.y && t == r.x;}
} p[maxn << 1], tmp[maxn << 1];
inline double dis(P a, P b){return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));}
inline bool cmp(P a, P b){return a.y < b.y;}
int n;
double dc(int L = 1, int R = n)
{
    if(L == R || (L + 1 == R && p[L].t == p[R].t)) return INF;
    if(L + 1 == R) return dis(p[L], p[R]);
    int M = (L + R) >> 1;
    double ans = min(dc(L, M), dc(M + 1, R));
    int k = 0;
    for(int i = L; i <= R; ++i) if(abs(p[M].x - p[L].x) <= ans)
        tmp[k++] = p[i];
    sort(tmp, tmp + k, cmp);
    for(int i = 0; i < k; ++i) for(int j = i; j < k && tmp[j].y - tmp[i].y < ans; ++j) if(tmp[i].t != tmp[j].t)
        ans = min(ans, dis(tmp[i], tmp[j]));
    return ans;
}
int main()
{
    int t; scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y), p[i].t = 0;
        n += n;
        for(int i = n / 2 + 1; i <= n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y), p[i].t = 1;
        sort(p + 1, p + n + 1);
        //n = unique(p + 1, p + n + 1) - p;
        printf("%.3lf\n", dc());
    }
    return 0;
}

AOJ CGL_4_B

卡壳裸题。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 8e4 + 5;
struct P
{
    double x, y;
    P(double a = .0, double b = .0){x = a, y = b;}
    P operator-(const P& r){return P(x - r.x, y - r.y);}
    double operator*(const P& r){return x * r.y - y * r.x;}
    bool operator<(const P& r){return x == r.x ? y < r.y : x < r.x;}
} p[maxn];
inline double dis(P a, P b){return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));}
int main()
{
    int n; scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);
    int i = 0, j = 0;
    for(int k = 0; k < n; ++k)
    {
        if(p[k] < p[i]) i = k;
        if(p[j] < p[k]) j = k;
    }
    int si = i, sj = j;
    double ret = .0;
    while(i != sj || j != si)
    {
        ret = max(ret, dis(p[i], p[j]));
        if((p[(i + 1) % n] - p[i]) * (p[(j + 1) % n] - p[j]) < 0) (++i) %= n;
        else (++j) %= n;
    }
    printf("%.7lf\n", ret);
    return 0;
}

POJ 2187

求包后卡壳。注意退化情况。

Code

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 5e4 + 5;
struct P
{
    int x, y;
    P(int a = 0, int b = 0){x = a, y = b;}
    P operator-(const P& r){return P(x - r.x, y - r.y);}
    int operator*(const P& r){return x * r.y - y * r.x;}
    bool operator<(const P& r)const{return x == r.x ? y < r.y : x < r.x;}
} p[maxn], h[maxn];
inline int dis(P l, P r){return (r.x - l.x) * (r.x - l.x) + (r.y - l.y) * (r.y - l.y);}
int main()
{
    int n; read(n);
    for(int i = 0; i < n; ++i) read(p[i].x, p[i].y);
    sort(p, p + n);
    h[0] = p[0], h[1] = p[1]; int k = 2;
    for(int i = 2; i < n; ++i)
    {
        while(k > 1 && (p[i] - h[k - 2]) * (h[k - 1] - h[k - 2]) <= 0) --k;
        h[k++] = p[i];
    }
    int kk = k; h[kk++] = p[n - 2];
    for(int i = n - 3; ~i; --i)
    {
        while(kk > k && (p[i] - h[kk - 2]) * (h[kk - 1] - h[kk - 2]) <= 0) --kk;
        h[kk++] = p[i];
    }
    if(kk > 2) kk--;
    if(kk == 2)
    {
        printf("%d\n", dis(h[0], h[1]));
        return 0;
    }
    int i = 0, j = 0;
    for(int l = 0; l < kk; ++l){if(h[l] < h[i]) i = l; if(h[j] < h[l]) j = l;}
    int si = i, sj = j, ret = 0;
    while(i != sj || j != si)
    {
        ret = max(ret, dis(h[i], h[j]));
        if((h[(i + 1) % kk] - h[i]) * (h[(j + 1) % kk] - h[j]) > 0) (++i) %= kk;
        else (++j) %= kk;
    }
    printf("%d\n", ret);
}

LA 4728

求出各个端点后上凸包直径。

Code

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 5e5 + 5;
struct P
{
    int x, y;
    P(int a = 0, int b = 0){x = a, y = b;}
    P operator-(const P& r){return P(x - r.x, y - r.y);}
    int operator*(const P& r){return x * r.y - y * r.x;}
    bool operator<(const P& r)const{return x == r.x ? y < r.y : x < r.x;}
} p[maxn], h[maxn];
inline int dis(P l, P r){return (r.x - l.x) * (r.x - l.x) + (r.y - l.y) * (r.y - l.y);}
int main()
{
    int t; read(t);
    while(t--)
    {
        int n; read(n);
        for(int i = 0, x, y, w; i < n; ++i) 
            read(x, y, w), p[i * 4] = P(x, y), p[i * 4 + 1] = P(x + w, y), p[i * 4 + 2] = P(x, y + w), p[i * 4 + 3] = P(x + w, y + w);
        n *= 4;
        sort(p, p + n);
        h[0] = p[0], h[1] = p[1]; int k = 2;
        for(int i = 2; i < n; ++i)
        {
            while(k > 1 && (p[i] - h[k - 2]) * (h[k - 1] - h[k - 2]) <= 0) --k;
            h[k++] = p[i];
        }
        int kk = k; h[kk++] = p[n - 2];
        for(int i = n - 3; ~i; --i)
        {
            while(kk > k && (p[i] - h[kk - 2]) * (h[kk - 1] - h[kk - 2]) <= 0) --kk;
            h[kk++] = p[i];
        }
        if(kk > 2) kk--;
        if(kk == 2)
        {
            printf("%d\n", dis(h[0], h[1]));
            return 0;
        }
        int i = 0, j = 0;
        for(int l = 0; l < kk; ++l){if(h[l] < h[i]) i = l; if(h[j] < h[l]) j = l;}
        int si = i, sj = j, ret = 0;
        while(i != sj || j != si)
        {
            ret = max(ret, dis(h[i], h[j]));
            if((h[(i + 1) % kk] - h[i]) * (h[(j + 1) % kk] - h[j]) > 0) (++i) %= kk;
            else (++j) %= kk;
        }
        printf("%d\n", ret);
    }
    return 0;
}