POJ 1410 判断线段交和点在凸包内
1 #include2 #include 3 #include 4 #define MP make_pair 5 using namespace std; 6 typedef long long LL; 7 8 9 const double eps = 1e-8;10 11 int sgn(double x) {12 if (fabs(x) < eps) return 0;13 return x < 0 ? -1 : 1;14 }15 16 17 struct Point {18 double x, y;19 Point(double x = 0, double y = 0) : x(x), y(y) {}20 Point operator - (const Point &b) const {21 return Point(x - b.x, y - b.y);22 }23 double operator ^ (const Point &b) const {24 return x * b.y - y * b.x;25 }26 double operator *(const Point &b) const {27 return x * b.x + y * b.y;28 }29 };30 31 struct Line {32 Point s, e;33 Line(Point s, Point e): s(s), e(e) {}34 };35 36 bool SI(Line l1, Line l2) {37 return max(l1.s.x, l1.e.x) >= min(l2.s.x, l2.e.x)38 && max(l2.s.x, l2.e.x) >= min(l1.s.x, l1.e.x)39 && max(l1.s.y, l1.e.y) >= min(l2.s.y, l2.e.y)40 && max(l2.s.y, l2.e.y) >= min(l1.s.y, l1.e.y)41 && sgn((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 42 && sgn((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn((l1.e - l2.e) ^ (l2.s - l2.e));43 }44 45 bool onSeg(Point P, Line L) {46 return sgn((L.s - P) ^ (L.e - P)) == 047 && sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 048 && sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0;49 }50 51 int inConvexPoly(Point a, Point p[], int n) {52 for (int i = 0; i < n; i++) {53 if (sgn((p[i] - a) ^ (p[(i + 1) % n] - a)) < 0) return -1;54 else if (onSeg(a, Line(p[i], p[(i + 1) % n]))) return 0;55 }56 return 1;57 }58 59 int main() {60 int T;61 double x1, y1, x2, y2;62 scanf("%d", &T);63 while (T--) {64 scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);65 Line line = Line(Point(x1, y1), Point(x2, y2));66 scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);67 if (x1 > x2) swap(x1, x2);68 if (y1 > y2) swap(y1, y2);69 Point p[10];70 p[0] = Point(x1, y1);71 p[1] = Point(x2, y1);72 p[2] = Point(x2, y2);73 p[3] = Point(x1, y2);74 if (SI(line, Line(p[0], p[1]))) {puts("T"); continue;}75 if (SI(line, Line(p[1], p[2]))) {puts("T"); continue;}76 if (SI(line, Line(p[2], p[3]))) {puts("T"); continue;}77 if (SI(line, Line(p[3], p[0]))) {puts("T"); continue;}78 if (inConvexPoly(line.s, p, 4) >= 0 || inConvexPoly(line.e, p, 4) >= 0) {79 puts("T");80 continue;81 }82 puts("F");83 }84 85 return 0;86 }
POJ 2546 求两圆的面积交
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 typedef long long LL; 7 8 const double eps = 1e-6; 9 const double pi = acos(-1.0);10 11 struct Circle {12 double x, y;13 double r;14 Circle(double x = 0.0, double y = 0.0, double r = 1.0) : x(x), y(y), r(r) {}15 };16 17 double insectArea(Circle a, Circle b) {18 double dis = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));19 if (a.r + b.r <= dis) {20 return 0.0;21 } else if (fabs(a.r - b.r) >= dis) {22 return pi * min(a.r, b.r) * min(a.r, b.r);23 } else {24 double B1 = acos((a.r * a.r + dis * dis - b.r * b.r) / (2.0 * a.r * dis));25 double B2 = acos((b.r * b.r + dis * dis - a.r * a.r) / (2.0 * b.r * dis));26 return B1 * a.r * a.r + B2 * b.r * b.r - dis * a.r * sin(B1);27 }28 }29 30 int main() {31 double x, y, r;32 scanf("%lf%lf%lf", &x, &y, &r);33 Circle c1 = Circle(x, y, r);34 scanf("%lf%lf%lf", &x, &y, &r);35 Circle c2 = Circle(x, y, r);36 printf("%.3lf\n", insectArea(c1, c2));37 return 0;38 }
POJ 2187 对踵点对模板题
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 typedef long long LL; 7 8 const double eps = 1e-6; 9 const int maxn = 5e4 + 10;10 11 int n;12 double x, y;13 14 int sgn(double x) {15 if (fabs(x) < eps) return 0;16 return x < 0 ? -1 : 1;17 }18 19 struct Point {20 double x, y;21 Point(double x = 0, double y = 0): x(x), y(y) {}22 Point operator - (const Point &b) const {23 return Point(x - b.x, y - b.y);24 }25 double operator ^ (const Point &b) const {26 return x * b.y - y * b.x;27 } 28 double operator * (const Point &b) const {29 return x * b.x + y * b.y;30 }31 };32 33 bool cmp(const Point &a, const Point &b) {34 return sgn(a.x - b.x) == 0 ? (a.y < b.y) : (a.x < b.x);35 }36 37 double dist(Point a, Point b) {38 return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) ;39 }40 41 Point p[maxn], ch[maxn];42 43 int ConvexHull() {44 sort(p, p + n, cmp);45 int m = 0;46 for (int i = 0; i < n; i++) {47 while (m > 1 && sgn((ch[m - 1] - ch[m - 2]) ^ (p[i] - ch[m - 2])) <= 0) m--;48 ch[m++] = p[i];49 }50 int k = m;51 for (int i = n - 2; i >= 0; i--) {52 while (m > k && sgn((ch[m - 1] - ch[m - 2]) ^ (p[i] - ch[m - 2])) <= 0) m--;53 ch[m++] = p[i];54 }55 if (n > 1) m--;56 return m;57 }58 59 void solve() {60 int m = ConvexHull();61 if (m == 2) {62 printf("%.0lf\n", dist(ch[0], ch[1]));63 } else {64 int i = 0, j = 0;65 for (int k = 0; k < m; k++) {66 if (!cmp(ch[i], ch[k])) i = k;67 if (cmp(ch[j], ch[k])) j = k;68 }69 double res = 0.0;70 int si = i, sj = j;71 while (si != j || sj != i) {72 res = max(res, dist(ch[i], ch[j]));73 double tmp = (ch[(i + 1) % m] - ch[i]) ^ (ch[(j + 1) % m] - ch[j]);74 if (sgn(tmp) < 0) {75 i = (i + 1) % m;76 } else {77 j = (j + 1) % m;78 }79 }80 printf("%.0lf\n", res);81 }82 83 }84 85 int main() {86 scanf("%d", &n);87 for (int i = 0; i < n; i++) {88 scanf("%lf%lf", &x, &y);89 p[i].x = x; p[i].y = y;90 }91 solve();92 93 return 0;94 }
POJ 1584 判断凸多边形，点在多边形内；计算点到线段距离(但事实上思考一下就会发现直接求点到直线距离即可)
1 #include2 #include 3 #include 4 using namespace std; 5 6 typedef long long LL; 7 8 const double eps = 1e-8; 9 const double pi = acos(-1.0); 10 11 int sgn(double x) { 12 if (fabs(x) < eps) return 0; 13 return x < 0 ? -1 : 1; 14 } 15 16 struct Point { 17 double x, y; 18 Point(double x = 0.0, double y = 0.0): x(x), y(y) {} 19 Point operator - (const Point &b) const { 20 return Point(x - b.x, y - b.y); 21 } 22 double operator ^ (const Point &b) const { 23 return x * b.y - y * b.x; 24 } 25 double operator * (const Point &b) const { 26 return x * b.x + y * b.y; 27 } 28 }; 29 30 struct Line { 31 Point s, e; 32 Line() {} 33 Line(Point s, Point e) : s(s), e(e) {} 34 }; 35 36 double dist(Point a, Point b) { 37 double t = (a - b) * (a - b); 38 return sqrt(t); 39 } 40 41 bool isCH(Point poly[], int n) { 42 bool s[3]; 43 s[0] = s[1] = s[2] = false; 44 for (int i = 0; i < n; i++) { 45 s[sgn((poly[(i + 1) % n] - poly[i]) ^ (poly[(i + 2) % n] - poly[i])) + 1] = true; 46 if (s[0] && s[2]) return false; 47 } 48 return true; 49 } 50 51 Point PTS(Point P, Line L) { 52 Point result; 53 Point v = L.e - L.s; 54 double t = (P - L.s) * v / (v * v); 55 // if (t >= 0 && t <= 1) { 56 result.x = L.s.x + t * v.x; 57 result.y = L.s.y + t * v.y; 58 // } else { 59 // if (dist(P, L.s) < dist(P, L.e)) result = L.s; 60 // else result = L.e; 61 // } 62 return result; 63 } 64 65 bool onSeg(Point P, Line L) { 66 return sgn((L.s - P) ^ (L.e - P)) == 0 67 && sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0 68 && sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0; 69 } 70 71 int inCP(Point a, Point p[], int n) { 72 for (int i = 0; i < n; i++) { 73 if (sgn((p[i] - a) ^ (p[(i + 1) % n] - a)) < 0) return -1; 74 else if (onSeg(a, Line(p[i], p[(i + 1) % n]))) return 0; 75 } 76 return 1; 77 } 78 79 bool inter(Line l1, Line l2) { 80 return max(l1.s.x, l1.e.x) >= min(l2.s.x, l2.e.x) 81 && max(l2.s.x, l2.e.x) >= min(l1.s.x, l1.e.x) 82 && max(l1.s.y, l1.e.y) >= min(l2.s.y, l2.e.y) 83 && max(l2.s.y, l2.e.y) >= min(l1.s.y, l1.e.y) 84 && sgn((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 85 && sgn((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0; 86 } 87 88 int inPoly(Point P, Point poly[], int n) { 89 int cnt = 0; 90 Line ray, side; 91 ray.s = P; 92 ray.e.y = P.y; 93 ray.e.x = -100000000000.0; 94 95 for (int i = 0; i < n; i++) { 96 side.s = poly[i]; 97 side.e = poly[(i + 1) % n]; 98 99 if (onSeg(P,side)) return 0;100 if (sgn(side.s.y - side.e.y) == 0) continue;101 if(onSeg(side.s,ray)) {102 if(sgn(side.s.y - side.e.y) > 0) cnt++;103 } else if(onSeg(side.e,ray)) {104 if(sgn(side.e.y - side.s.y) > 0)cnt++;105 } else if(inter(ray,side)) {106 cnt++;107 }108 }109 if (cnt % 2 == 1) return 1;110 else return -1;111 }112 113 114 Point p[110];115 int main() {116 int n;117 double R,x,y;118 while (scanf("%d",&n) == 1) {119 if (n < 3) break;120 scanf("%lf%lf%lf", &R, &x, &y);121 for (int i = 0; i < n; i++) {122 scanf("%lf%lf", &p[i].x, &p[i].y);123 }124 if (!isCH(p, n)) {125 puts("HOLE IS ILL-FORMED");126 continue;127 }128 Point P = Point(x, y);129 bool flag = true;130 if (inPoly(P, p, n) >= 0) {131 for (int i = 0; i < n && flag; i++) {132 if (sgn(dist(P, PTS(P, Line(p[i], p[(i + 1) % n]))) - R) < 0) {133 flag = false;134 }135 }136 } else {137 flag = false;138 }139 if (flag) {140 puts("PEG WILL FIT");141 } else {142 puts("PEG WILL NOT FIT");143 }144 }145 return 0;146 }
POJ 1873 枚举加凸包模板
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 typedef long long LL; 7 8 const double eps = 1e-8; 9 10 int sgn(double x) { 11 if (fabs(x) < eps) return 0; 12 return x < 0 ? -1 : 1; 13 } 14 15 struct Point { 16 double x, y, l; 17 int v; 18 Point(double x = 0.0, double y = 0.0) : x(x), y(y) {} 19 Point operator - (const Point &b) const { 20 return Point(x - b.x, y - b.y); 21 } 22 double operator ^ (const Point &b) const { 23 return x * b.y - y * b.x; 24 } 25 double operator * (const Point &b) const { 26 return x * b.x + y * b.y; 27 } 28 }; 29 30 bool cmp(const Point &a, const Point &b) { 31 return sgn(a.x - b.x) == 0 ? (a.y < b.y) : (a.x < b.x); 32 } 33 34 double dist(Point a, Point b) { 35 Point c = a - b; 36 return sqrt(c * c); 37 } 38 39 Point p[20], ch[20]; 40 Point pp[20]; 41 42 43 int ConvexHull(int m) { 44 sort(pp, pp + m, cmp); 45 int num = 0; 46 for (int i = 0; i < m; i++) { 47 while (num > 1 && sgn((ch[num - 1] - ch[num - 2]) ^ (pp[i] - ch[num - 2])) <= 0) num--; 48 ch[num++] = pp[i]; 49 } 50 int k = num; 51 for (int i = m - 2; i >= 0; i--) { 52 while (num > k && sgn((ch[num - 1] - ch[num - 2]) ^ (pp[i] - ch[num - 2])) <= 0) num--; 53 ch[num++] = pp[i]; 54 } 55 if (m > 1) num--; 56 return num; 57 } 58 59 int n; 60 int cnt; 61 double ans_l; 62 int ans_v, ans_c; 63 64 int ans; 65 66 67 void init() { 68 ans = 0; 69 ans_v = 200000.0; 70 ans_l = 0.0; 71 ans_c = 20; 72 } 73 74 void solve() { 75 for (int bit = (1 << n) - 1; bit ; bit--) { 76 int cnt = 0; 77 double l = 0.0; 78 double c = 0.0; 79 int v = 0; 80 for (int i = 0; i < n; i++) { 81 if (bit & (1 << i)) { 82 l += p[i].l; 83 v += p[i].v; 84 } else { 85 pp[cnt++] = p[i]; 86 } 87 } 88 cnt = ConvexHull(cnt); 89 90 for (int i = 0; i < cnt; i++) { 91 c += dist(ch[i], ch[(i + 1) % cnt]); 92 } 93 bool flag = false; 94 if (sgn(l - c) >= 0) { 95 if (v < ans_v) { 96 flag = true; 97 } else if (v == ans_v) { 98 if (cnt <= ans_c) flag = true; 99 }100 }101 if (flag) {102 ans_v = v; ans_c = cnt;103 ans = bit;104 ans_l = l - c;105 }106 }107 }108 109 int main() {110 double x, y, l;111 int v;112 int te = 0;113 while (scanf("%d", &n), n) {114 init();115 for (int i = 0; i < n; i++) {116 scanf("%lf%lf%d%lf", &p[i].x, &p[i].y, &p[i].v, &p[i].l);117 }118 solve();119 printf("Forest %d\n", ++te);120 printf("Cut these trees:");121 for (int i = 0; i < 15; i++) {122 if (ans & (1 << i)) {123 printf(" %d", i + 1);124 }125 }puts("");126 printf("Extra wood: %.2lf\n\n", ans_l);127 }128 return 0;129 }
HDU 3007 最小圆覆盖模板题
1 #include2 #include 3 #include 4 using namespace std; 5 typedef long long LL; 6 7 const double eps = 1e-6; 8 9 int sgn(double x) {10 if (fabs(x) < eps) return 0;11 return x < 0 ? -1 : 1;12 }13 14 struct Point {15 double x, y;16 Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}17 Point operator - (const Point &b) const {18 return Point(x - b.x, y - b.y);19 } 20 Point operator + (const Point &b) const {21 return Point(x + b.x, y + b.y);22 }23 double operator ^ (const Point &b) const {24 return x * b.y - y * b.x;25 }26 double operator * (const Point &b) const {27 return x * b.x + y * b.y;28 }29 Point operator / (double times) const {30 return Point(x / times, y / times);31 }32 Point operator * (double times) const {33 return Point(x * times, y * times);34 }35 };36 37 Point center;38 39 Point outer(Point a, Point b, Point c) {40 double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;41 double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;42 double d = a1 * b2 - a2 * b1;43 return Point(a.x - (c2 * b1 - c1 * b2) / d, a.y + (a1 * c2 - a2 * c1) / d);44 }45 46 double dis(Point a, Point b) {47 return sqrt((a - b) * (a - b));48 }49 50 int n;51 52 Point p[510];53 double r;54 55 void solve() {56 r = 0;57 center = p[0];58 for (int i = 1; i < n; i++) {59 if (sgn(dis(center, p[i]) - r) > 0) {60 center = p[i]; r = 0;61 for (int j = 0; j < i; j++) {62 if (sgn(dis(center, p[j]) - r) > 0) {63 center = (p[i] + p[j]) / 2;64 r = dis(p[i], center);65 for (int k = 0; k < j; k++) {66 if (sgn(dis(center, p[k]) - r) > 0) {67 center = outer(p[i], p[j], p[k]);68 r = dis(center, p[k]);69 }70 }71 }72 }73 }74 }75 printf("%.2lf %.2lf %.2lf\n", center.x, center.y, r);76 }77 78 int main() {79 while (scanf("%d", &n), n) {80 for (int i = 0; i < n; i++) {81 scanf("%lf%lf", &p[i].x, &p[i].y);82 }83 solve();84 }85 return 0;86 }
POJ 3568 求两个凸包间
1 #include2 #include 3 #include 4 using namespace std; 5 typedef long long LL; 6 7 const double eps = 1e-6; 8 const int maxn = 1e4 + 10; 9 const double INF = 1e20; 10 11 int sgn(double x) { 12 if (fabs(x) < eps) return 0; 13 return x < 0 ? -1 : 1; 14 } 15 16 struct Point { 17 double x, y; 18 Point(double x = 0, double y = 0): x(x), y(y) {} 19 Point operator - (const Point &b) const { 20 return Point(x - b.x, y - b.y); 21 } 22 double operator * (const Point &b) const { 23 return x * b.x + y * b.y; 24 } 25 double operator ^ (const Point &b) const { 26 return x * b.y - y * b.x; 27 } 28 }; 29 30 bool cmp(const Point &a, const Point &b) { 31 return sgn(a.x - b.x) == 0 ? (a.y < b.y) : (a.x < b.x); 32 } 33 34 double dist(Point a, Point b) { 35 double t = (a - b) * (a - b); 36 return sqrt(t); 37 } 38 39 struct Line { 40 Point s, e; 41 Line(Point s, Point e): s(s), e(e) {} 42 }; 43 44 Point PST(Point P, Line l) { 45 Point result; 46 Point v = l.e - l.s; 47 double t = (P - l.s) * v / (v * v); 48 if (0 <= t && t <= 1) { 49 result.x = l.s.x + t * v.x; 50 result.y = l.s.y + t * v.y; 51 } else { 52 if (dist(P, l.s) < dist(P, l.e)) result = l.s; 53 else result = l.e; 54 } 55 return result; 56 } 57 58 double _PTS(Point p0, Point p1, Point p2) { 59 return dist(p0, PST(p0, Line(p1, p2))); 60 } 61 62 double STS(Point p0, Point p1, Point p2, Point p3) { 63 double ans1 = min(_PTS(p0, p2, p3), _PTS(p1, p2, p3)); 64 double ans2 = min(_PTS(p2, p0, p1), _PTS(p3, p0, p1)); 65 return min(ans1, ans2); 66 } 67 68 69 int ConvexHull(Point pp[], int m, Point ch[]) { 70 sort(pp, pp + m, cmp); 71 int num = 0; 72 for (int i = 0; i < m; i++) { 73 while (num > 1 && sgn((ch[num - 1] - ch[num - 2]) ^ (pp[i] - ch[num - 2])) <= 0) num--; 74 ch[num++] = pp[i]; 75 } 76 int k = num; 77 for (int i = m - 2; i >= 0; i--) { 78 while (num > k && sgn((ch[num - 1] - ch[num - 2]) ^ (pp[i] - ch[num - 2])) <= 0) num--; 79 ch[num++] = pp[i]; 80 } 81 if (m > 1) num--; 82 return num; 83 } 84 85 86 double getAngle(Point a1, Point a2, Point b1, Point b2) { 87 return (a2 - a1) ^ (b1 - b2); 88 } 89 90 double rotating(Point *p, int np, Point *q, int nq) { 91 int sp = 0, sq = 0; 92 for (int i = 0; i < np; i++) { 93 if (sgn(p[i].y - p[sp].y) < 0) sp = i; 94 } 95 for (int i = 0; i < nq; i++) { 96 if (sgn(q[i].y - q[sq].y) > 0) sq = i; 97 } 98 double tmp; 99 double ans = INF;100 101 for (int i = 0; i < np; i++) {102 while (sgn(tmp = getAngle(p[sp], p[(sp + 1) % np], q[sq], q[(sq + 1) % nq])) < 0) {103 sq = (sq + 1) % nq;104 }105 if (sgn(tmp) == 0) {106 ans = min(ans, STS(p[sp], p[(sp + 1) % np], q[sq], q[(sq + 1) % nq]));107 } else {108 ans = min(ans, _PTS(q[sq], p[sp], p[(sp + 1) % np]));109 }110 sp = (sp + 1) % np;111 }112 return ans;113 }114 115 116 Point p1[maxn], p2[maxn];117 Point ch1[maxn], ch2[maxn];118 119 120 double solve(Point *p, int n, Point *q, int m) {121 n = ConvexHull(p1, n, ch1);122 m = ConvexHull(p2, m, ch2);123 return min(rotating(ch1, n, ch2, m), rotating(ch2, m, ch1, n));124 }125 126 int main() {127 int n, m;128 while (scanf("%d%d", &n, &m), n && m) {129 for (int i = 0; i < n; i++) {130 scanf("%lf%lf", &p1[i].x, &p1[i].y);131 }132 for (int i = 0; i < m; i++) {133 scanf("%lf%lf", &p2[i].x, &p2[i].y);134 }135 double ans = solve(p1, n, p2, m);136 printf("%.5lf\n", ans);137 }138 return 0;139 }
POJ 1696 极角排序
POJ 1228 稳定凸包
POJ 3525 半平面交 求凸多边形内部点到边界最大距离
uva 4642 给出三角形三个顶点，求出三个圆的半径，三个圆满足两两相切且都与三角形相切
POJ 1981 问一个单位圆最多能覆盖多少个给出的点(n<=300)
HDU 6097 圆的反演基础题
uva 4676 给定两个三角形速度和顶点，求相撞时刻