分类 POJ 下的文章

Circular Area

题目链接

[POJ 2546] Circular Area

题解

中档题。题意大概是给定两个圆,求出相交的面积。
模板题。

代码

#include <cmath>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
const double pi = acos(-1.0);

struct Point {
    double x, y;
};

struct Circle {
    double r;
    Point center;
}a, b;

inline double squ(double a) {
    return a * a;
}

inline double dis(Point a, Point b) {
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

int main() {
    while (cin >> a.center.x >> a.center.y >> a.r >> b.center.x >> b.center.y >> b.r) {
        double length = dis(a.center, b.center);
        if (a.r + b.r < length) {
            printf("%.3lf\n", 0.0);
            continue;
        }
        if (fabs(a.r - b.r) >= length) {
            printf("%.3lf\n", pi * squ(min(a.r, b.r)));
            continue;
        }
        double angleA = acos((squ(a.r) + squ(length) - squ(b.r)) / 2 / a.r / length);
        double angleB = acos((squ(b.r) + squ(length) - squ(a.r)) / 2 / b.r / length);
        double area1 = squ(a.r) * angleA;
        double area2 = squ(b.r) * angleB;
        printf("%.3lf\n", area1 + area2 - a.r * length * sin(angleA));
    }
    return 0;
}

Beauty Contest

题目链接

[POJ 2187] Beauty Contest

题解

简单题。题意大概是给定一些平面上的点,求出给定点之间的最远点对并输出距离的平方。
旋转卡壳模板题。

代码

#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn = 50000 + 10;
int n, m;

inline double sqr(const double & a) {
    return a * a;
}

class Point {
public:
    double x, y;
    Point() {};

    Point(double _x, double _y) {
        x = _x;
        y = _y;
    }

    Point operator - (const Point & B) const {
        return Point(x - B.x, y - B.y);
    }

}input[maxn], tb[maxn];

bool cmp(Point p1, Point p2) {
    if (p1.x == p2.x) return p1.y < p2.y;
    return p1.x < p2.x;
}

int sqrdis(Point A, Point B) {
    return (A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y);
}

double Cross(Point A, Point B) {
    return A.x*B.y - A.y*B.x;
}

void ConvexHull() {
    sort(input, input + n, cmp);
    m = 0;
    for (int i = 0; i < n; i++) {
        while (m > 1 && Cross(tb[m - 1] - tb[m - 2], input[i] - tb[m - 2]) <= 0) m--;
        tb[m++] = input[i];
    }
    int k = m;
    for (int i = n - 2; i >= 0; i--) {
        while (m > k && Cross(tb[m - 1] - tb[m - 2], input[i] - tb[m - 2]) <= 0) m--;
        tb[m++] = input[i];
    }
    if (n > 1) m--;
}

int rotating_calipers() {
    int q = 1;
    int ans = 0;
    tb[m] = tb[0];
    for (int i = 0; i < m; i++) {
        while (Cross(tb[i + 1] - tb[i], tb[q + 1] - tb[i]) > Cross(tb[i + 1] - tb[i], tb[q] - tb[i]))
            q = (q + 1) % m;
        ans = max(ans, max(sqrdis(tb[i], tb[q]), sqrdis(tb[i + 1], tb[q + 1])));
    }
    return ans;
}

int main() {
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++)
            cin >> input[i].x >> input[i].y;
        ConvexHull();
        cout << rotating_calipers() << endl;
    }
    return 0;
}

A Round Peg in a Ground Hole

题目链接

[POJ 1584] A Round Peg in a Ground Hole

题解

中档题。题意大概是给定一组多边形,首先判断其是不是凸多边形,其次判断给定圆的圆心是否在多边形内,最后判断圆心到所有边的距离是否大于给定的半径。

代码

#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;

const double eps = 1e-10;
int n;
double r;
struct Point {
    double x, y;
} dimp;
vector<Point>vec;

inline int flag(double x) {
    return x > eps ? 1 : (x < -eps ? 2 : 0);
}

double Cross(Point p1, Point p2, Point p0) {
    return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

bool isConvex() {
    int i, s[3] = { 1,1,1 };
    for (i = 0; i<n&&s[1] | s[2]; i++) {
        s[flag(Cross(vec[(i + 1) % n], vec[(i + 2) % n], vec[i]))] = 0;
    }
    return s[1] | s[2];
}

int isInside(Point q) {
    int i, s[3] = { 1,1,1 };
    for (i = 0; i<n&&s[1] | s[2]; i++) {
        s[flag(Cross(vec[(i + 1) % n], q, vec[i]))] = 0;
    }
    return s[0] && (s[1] | s[2]);
}

double dis(Point a, Point b) {
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

Point inter(Point u1, Point u2, Point v1, Point v2) {
    Point ret = u1;
    double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x))
        / ((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x));
    ret.x += (u2.x - u1.x)*t;
    ret.y += (u2.y - u1.y)*t;
    return ret;
}

Point lineCross(Point p, Point l1, Point l2) {
    Point t = p;
    t.x += l1.y - l2.y;
    t.y += l2.x - l1.x;
    if (Cross(l1, t, p)*Cross(l2, t, p)>eps)
        return dis(p, l1)<dis(p, l2) ? l1 : l2;
    return inter(p, t, l1, l2);
}

int main() {
    while (cin >> n) {
        if (n<3)break;
        vec.clear();
        cin >> r >> dimp.x >> dimp.y;
        Point input;
        for (int i = 0; i<n; i++) {
            cin >> input.x >> input.y;
            vec.push_back(input);
        }
        if (!isConvex()) {
            cout << "HOLE IS ILL-FORMED" << endl;
            continue;
        }
        if (!isInside(dimp)) {
            cout << "PEG WILL NOT FIT" << endl;
            continue;
        }
        bool temp(false);
        for (int i = 0; i<n; i++) {
            input = lineCross(dimp, vec[i], vec[(i + 1) % n]);
            double dist = dis(input, dimp);
            if (dist<r) {
                temp = true;
                break;
            }
        }
        if (temp)cout << "PEG WILL NOT FIT" << endl;
        else  cout << "PEG WILL FIT" << endl;
    }
    return 0;
}

Intersection

题目链接

[POJ 1410] Intersection

题解

简单题。给定一个线段与一个矩形,判断它们有无公共点。
计算几何基础,首先判断线段是否在矩形内部,其次判断它们有无交点。

代码

#include <iostream>
#include <algorithm>
using namespace std;

const long long INF = 1ll << 60;
long double T, x1, x2, yy1, y2, l, r, t, d;

int main() {
    cin >> T;
    while (T--) {
        cin >> x1 >> yy1 >> x2 >> y2 >> l >> t >> r >> d;
        if (l > r)swap(l, r);
        if (d > t)swap(d, t);
        if (x1 <= r && x2 <= r && yy1 <= t && y2 <= t && x1 >= l && x2 >= l && yy1 >= d && y2 >= d) {
            cout << "T" << endl;
            continue;
        }
        if (x1 == x2) {
            if (x1 >= l && x1 <= r && max(yy1, y2) >= d && min(yy1, y2) <= t) {
                cout << 'T' << endl;
            }
            else cout << 'F' << endl;
            continue;
        }
        if (yy1 == y2) {
            if (yy1 >= d && yy1 <= t && max(x1, x2) >= l && min(x1, x2) <= r) {
                cout << 'T' << endl;
            }
            else cout << 'F' << endl;
            continue;
        }
        long double temp;
        temp = (t - y2) / (yy1 - y2)*(x1 - x2) + x2;
        if (temp >= min(x1, x2) && temp <= max(x1, x2) && temp >= l && temp <= r) {
            cout << "T" << endl;
            continue;
        }
        temp = (d - y2) / (yy1 - y2)*(x1 - x2) + x2;
        if (temp >= min(x1, x2) && temp <= max(x1, x2) && temp >= l && temp <= r) {
            cout << "T" << endl;
            continue;
        }
        temp = (l - x2) / (x1 - x2)*(yy1 - y2) + y2;
        if (temp >= min(yy1, y2) && temp <= max(yy1, y2) && temp >= d && temp <= t) {
            cout << "T" << endl;
            continue;
        }
        temp = (r - x2) / (x1 - x2)*(yy1 - y2) + y2;
        if (temp >= min(yy1, y2) && temp <= max(yy1, y2) && temp >= d && temp <= t) {
            cout << "T" << endl;
            continue;
        }
        cout << "F" << endl;
    }
}