计算几何
#include <bits/stdc++.h>
#define rep(i, L, R) for (int i = L; i <= R; ++i)
using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const int N = 1e5 + 7;
inline int sgn(double x) {
if (fabs(x) < eps) return 0;
return x > 0 ? 1 : -1;
}
struct Point {
double x, y;
Point() = default;
Point(double x, double y) : x(x), y(y) {}
Point operator+(const Point &a) const { return Point(x + a.x, y + a.y); }
Point operator-(const Point &a) const { return Point(x - a.x, y - a.y); }
Point operator*(const double &k) const { return Point(k * x, k * y); }
double operator*(const Point &a) const { return x * a.x + y * a.y; }
double operator^(const Point &a) const { return x * a.y - y * a.x; }
Point operator/(double k) { return {x / k, y / k}; };
bool is_par(const Point &a) const { return abs((*this) ^ a) <= eps; }
double len2() const { return (*this) * (*this); }
double dis2(const Point &a) const { return (a - (*this)).len2(); }
};
struct Line {
Point p, v;
Line() = default;
Line(Point p, Point v) : p(p), v(v){};
Point inter(const Line &a) const {
return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v));
}
} line;
int dcmp(double x) {
if (fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
double dis(Point a, Point b) { return hypot(a.x - b.x, a.y - b.y); }
typedef Point vec;
double cross(vec a, vec b) { return a.x * b.y - a.y * b.x; } // 向量积
double S(Point *a, int n) { //数组起始位置 多边形有多少个点
double res = 0;
for (int i = 0; i < n; ++i) res += cross(a[i], a[(i + 1) % n]);
return res / 2; // 面积有正负
}
Point center(Point *a, int n) { // 求重心
Point ans = {0, 0};
double Sa = S(a, n);
if (Sa == 0) return ans;
for (int i = 0; i < n; ++i)
ans = ans + (a[i] + a[(i + 1) % n]) * cross(a[i], a[(i + 1) % n]);
return ans / Sa / 6;
}
// bool line_segment_intersect(Line L, Point A, Point B, Point &P) {
// Point a = A - L.B, b = L.A - L.B, c = B - L.B;
// if (dcmp(cross(a, b)) * dcmp(cross(b, c)) >= 0) {
// Point u = L.A - A;
// double t = cross(A - B, u) / cross(b, A - B);
// P = L.A + b * t;
// return true;
// }
// return false;
// }
bool isIN(Point A, Line L) {
double x = min(L.p.x, L.v.x);
double xx = max(L.p.x, L.v.x);
double y = min(L.p.y, L.v.y);
double yy = max(L.p.y, L.v.y);
return A.x <= xx and A.x >= x and A.y <= yy and A.y >= y;
}
bool isIN1(Point A, Point B, Point C) { return (B - A) * (A - C) >= -eps; }
Point a[N];
int T, n;
int main() {
cout << isIN({1, 1}, {{2, 2}, {3, 3}}) << endl;
cout << isIN({2, 2}, {{1, 1}, {3, 3}}) << endl;
Line a = {{0, 0}, {0, 2}};
Line b = {{1, 1}, {-1, 1}};
cout << a.inter(b).x << ' ' << a.inter(b).y << '\n';
// scanf("%d", &n);
// rep(i, 1, n) scanf("%lf%lf", &a[i].x, &a[i].y);
// Point o = center(a + 1, n);
// double ans = 1e18;
// rep(th, 0, 3600) {
// double x = o.x + cos(th * 1.0 / 10), y = o.y + sin(th * 1.0 / 10);
// Line lx = {o, Point{x, y}};
// Point P, Q;
// int f = 0;
// rep(i, 2, n) {
// Line ly = {a[i - 1], a[i]};
// Point T = lx.inter(ly);
// // if (f == 0 and isIN(T, ly)) {
// // P = T;
// // ++f;
// // }
// // if (f == 1 and isIN(T, ly)) {
// // Q = T;
// // ++f;
// // break;
// // }
// if (f == 0 and isIN1(T, a[i - 1], a[i])) {
// P = T;
// ++f;
// }
// if (f == 1 and isIN1(T, a[i - 1], a[i])) {
// Q = T;
// ++f;
// break;
// }
// }
// if (f == 1) Q = lx.inter({a[n], a[1]}), ++f;
// // cerr << P.x << ' ' << P.y << endl;
// // if (dcmp(P.x) == 0 and dcmp(P.y) == 0)
// // cerr << Q.x << ' ' << Q.y << endl;
// if (f == 2) {
// double d = dis(P, Q);
// if (d > -1e18) ans = min(d, ans);
// }
// }
// cout << ans;
return 0;
} #include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
#define eps 1e-8
int n;
int dcmp(double x) {
if (fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
bool operator!=(const Point &p) {
return dcmp(x - p.x) != 0 || (dcmp(x - p.x) == 0 && dcmp(y - p.y) != 0);
}
friend Point operator+(Point A, Point B) {
return Point(A.x + B.x, A.y + B.y);
}
friend Point operator-(Point A, Point B) {
return Point(A.x - B.x, A.y - B.y);
}
friend Point operator*(Point A, double d) {
return Point(A.x * d, A.y * d);
}
friend Point operator/(Point A, double d) {
return Point(A.x / d, A.y / d);
}
} p[30];
struct Line {
Point A, B;
} line;
double dot(Point A, Point B) { return A.x * B.x + A.y * B.y; }
double cross(Point A, Point B) { return A.x * B.y - A.y * B.x; }
double polygon_area() {
double area = 0;
for (int i = 1; i < n - 1; i++) area += cross(p[i] - p[0], p[i + 1] - p[0]);
return fabs(area) / 2;
}
bool line_segment_intersect(Line L, Point A, Point B, Point &P) {
Point a = A - L.B, b = L.A - L.B, c = B - L.B;
if (dcmp(cross(a, b)) * dcmp(cross(b, c)) >= 0) {
Point u = L.A - A;
double t = cross(A - B, u) / cross(b, A - B);
P = L.A + b * t;
return true;
}
return false;
}
int main() {
Point a;
cout << line_segment_intersect({{1, 1}, {-1, 1}}, {0, 0}, {0, 2}, a)
<< endl;
cout << a.x << ' ' << a.y << endl;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
scanf("%lf%lf%lf%lf", &line.A.x, &line.A.y, &line.B.x, &line.B.y);
int flag = 0;
double sum1 = polygon_area(), sum2 = 0;
Point P, T;
p[n] = p[0];
for (int i = 0; i < n; i++) {
if (flag == 0 && line_segment_intersect(line, p[i], p[i + 1], P)) {
sum2 += cross(P, p[i + 1]);
flag++;
} else if (flag == 1 &&
line_segment_intersect(line, p[i], p[i + 1], T) && P != T) {
sum2 += cross(p[i], T);
sum2 += cross(T, P);
flag++;
break;
} else if (flag == 1)
sum2 += cross(p[i], p[i + 1]);
}
sum2 = fabs(sum2) / 2;
sum1 -= sum2;
if (sum1 < sum2) swap(sum1, sum2);
printf("%.0lf %.0lf\n", sum1, sum2);
return 0;
} #include <bits/stdc++.h>
#define rep(i, L, R) for (int i = L; i <= R; ++i)
using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const int N = 1000007;
inline int sgn(double x) {
if (fabs(x) < eps) return 0;
return x > 0 ? 1 : -1;
}
struct point {
double x, y;
point operator+(point b) { return {x + b.x, y + b.y}; };
point operator-(point b) { return {x - b.x, y - b.y}; };
point operator*(double k) { return {x * k, y * k}; };
point operator/(double k) { return {x / k, y / k}; };
};
struct Line {
point A, B;
} line;
int dcmp(double x) {
if (fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
double dis(point a, point b) { return hypot(a.x - b.x, a.y - b.y); }
typedef point vec;
double cross(vec a, vec b) { return a.x * b.y - a.y * b.x; }
double S(point *a, int n) { //数组起始位置 多边形有多少个点
double res = 0;
for (int i = 0; i < n; ++i) res += cross(a[i], a[(i + 1) % n]);
return res / 2; // 面积有正负
}
point center(point *a, int n) { // 求重心
point ans = {0, 0};
double Sa = S(a, n);
if (Sa == 0) return ans;
for (int i = 0; i < n; ++i)
ans = ans + (a[i] + a[(i + 1) % n]) * cross(a[i], a[(i + 1) % n]);
return ans / Sa / 6;
}
bool line_segment_intersect(Line L, point A, point B, point &P) {
point a = A - L.B, b = L.A - L.B, c = B - L.B;
if (dcmp(cross(a, b)) * dcmp(cross(b, c)) >= 0) {
point u = L.A - A;
double t = cross(A - B, u) / cross(b, A - B);
P = L.A + b * t;
return true;
}
return false;
}
point a[N];
int T, n;
int main() {
scanf("%d", &n);
rep(i, 1, n) scanf("%lf%lf", &a[i].x, &a[i].y);
point o = center(a + 1, n);
double ans = 1e18;
rep(th, 0, 3600) {
double x = o.x + cos(th * 1.0 / 10), y = o.y + sin(th * 1.0 / 10);
Line lx = {o, point{x, y}};
point P, Q;
int f = 0;
rep(i, 2, n) {
if (!f && line_segment_intersect(line, a[i - 1], a[i], P)) f = 1;
if (f) {
if (line_segment_intersect(line, a[i - 1], a[i], Q)) {
f = 2;
break;
}
}
}
if (f == 1) {
line_segment_intersect(line, a[n], a[1], Q);
}
double d = dis(P, Q);
ans = min(d, ans);
}
cout << ans;
return 0;
} 算法竞赛之路 文章被收录于专栏
整理、记录算法竞赛的好题
投递拼多多集团-PDD等公司10个岗位
