https://vjudge.net/contest/158543#overview
POJ 2318 叉乘
下边叉乘上边，结果为负，下边在上边的逆时针；结果为正，下边在上边的顺时针
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define PI 3.14159265358979323 #define EPS 1e-6 using namespace std; const int MAXN = 5005; int a[MAXN]; int n, m; int x1, yh, x2, yl; int ans[MAXN]; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1 : 0); } struct TPoint { double x, y; TPoint() {} TPoint(const double& _x, const double& _y): x(_x), y(_y) {} }upper[MAXN], lower[MAXN]; bool operator == (const TPoint& a, const TPoint& b) { return fabs(a.x - b.x) < EPS && fabs(a.y - b.y) < EPS; } bool operator != (const TPoint& a, const TPoint& b) { return fabs(a.x - b.x) > EPS || fabs(a.y - b.y) > EPS; } TPoint operator - (const TPoint& a, const TPoint& b) { return TPoint(a.x - b.x, a.y - b.y); } TPoint operator + (const TPoint& a, const TPoint& b) { return TPoint(a.x + b.x, a.y + b.y); } double cross(const TPoint& a, const TPoint &b) { return a.x * b.y - a.y * b.x; } double cross(const TPoint& a, const TPoint &b, const TPoint &c) { return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y); } int main() { //freopen("input.txt", "r", stdin); int u, l, r, mid; while(sf(n) && n != 0) { clr(ans, 0); sf(m); sf(x1); sf(yh); sf(x2); sf(yl); upper[0] = TPoint(x1, yh); lower[0] = TPoint(x1, yl); upper[n+1] = TPoint(x2, yh); lower[n+1] = TPoint(x2, yl); for(int i = 1; i <= n; i++) { sf(u); sf(l); upper[i] = TPoint(u, yh); lower[i] = TPoint(l, yl); } for(int i = 0; i < m; i++) { sf(l); sf(r); TPoint tmp = TPoint(l, r); l = 0, r = n + 2; while(true) { mid = (l + r) >> 1; int s1 = sign(cross(tmp, lower[mid], upper[mid])); int s2 = sign(cross(tmp, lower[mid+1], upper[mid+1])); if(s1 == -1 && s2 == 1) { ans[mid]++; break; } if(s1 == -1 && s2 == -1) { l = mid + 1; } else { r = mid; } } } for(int i = 0; i <= n; i++) { printf("%d: %d\n", i, ans[i]); } printf("\n"); } return 0; } POJ 2398 叉乘 #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<set> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define PI 3.14159265358979323 #define EPS 1e-6 using namespace std; const int MAXN = 1005; int a[MAXN]; int n, m; int x1, yh, x2, yl; int ans[MAXN]; int pr[MAXN]; set<int> S; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1 : 0); } struct TPoint { double x, y; TPoint() {} TPoint(const double& _x, const double& _y): x(_x), y(_y) {} }; struct Arc { TPoint upper, lower; Arc() {} Arc(const TPoint& a, const TPoint& b): upper(a), lower(b) {} bool operator < (const Arc& b) const { return upper.x < b.upper.x; } }arc[MAXN]; bool operator == (const TPoint& a, const TPoint& b) { return fabs(a.x - b.x) < EPS && fabs(a.y - b.y) < EPS; } bool operator != (const TPoint& a, const TPoint& b) { return fabs(a.x - b.x) > EPS || fabs(a.y - b.y) > EPS; } TPoint operator - (const TPoint& a, const TPoint& b) { return TPoint(a.x - b.x, a.y - b.y); } TPoint operator + (const TPoint& a, const TPoint& b) { return TPoint(a.x + b.x, a.y + b.y); } double cross(const TPoint& a, const TPoint &b) { return a.x * b.y - a.y * b.x; } double cross(const TPoint& a, const TPoint &b, const TPoint &c) { return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y); } int main() { //freopen("input.txt", "r", stdin); int u, l, r, mid; while(sf(n) && n != 0) { clr(ans, 0); clr(pr, 0); S.clear(); sf(m); sf(x1); sf(yh); sf(x2); sf(yl); arc[0].upper = TPoint(x1, yh); arc[0].lower = TPoint(x1, yl); arc[n+1].upper = TPoint(x2, yh); arc[n+1].lower = TPoint(x2, yl); for(int i = 1; i <= n; i++) { sf(u); sf(l); arc[i].upper = TPoint(u, yh); arc[i].lower = TPoint(l, yl); } sort(arc + 1, arc + n + 1); for(int i = 0; i < m; i++) { sf(l); sf(r); TPoint tmp = TPoint(l, r); l = 0, r = n + 2; while(true) { mid = (l + r) >> 1; int s1 = sign(cross(tmp, arc[mid].lower, arc[mid].upper)); int s2 = sign(cross(tmp, arc[mid+1].lower, arc[mid+1].upper)); if(s1 == -1 && s2 == 1) { ans[mid]++; break; } if(s1 == -1 && s2 == -1) { l = mid + 1; } else { r = mid; } } } for(int i = 0; i <= m; i++) { S.insert(ans[i]); pr[ans[i]]++; } printf("Box\n"); for(int i = 1; i <= m; i++) { if(S.count(i) == 1) printf("%d: %d\n", i, pr[i]); } } return 0; }POJ 3304 线段与直线
此题可以转化为是否有一条直线能与所有直线相交
要注意如果2个端点非常非常近，叉乘会导致这样的向量怎么乘都和其他线段共线，必须舍弃
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<set> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sfd(a) scanf("%lf", &a) #define PI 3.14159265358979323 #define EPS 1e-8 using namespace std; const int MAXN = 205; int a[MAXN]; int n, m; int x1, yh, x2, yl; int ans[MAXN]; int pr[MAXN]; set<int> S; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1 : 0); } struct TPoint { double x, y; TPoint() {} TPoint(const double& _x, const double& _y): x(_x), y(_y) {} }tp[MAXN]; bool operator == (const TPoint& a, const TPoint& b) { return fabs(a.x - b.x) < EPS && fabs(a.y - b.y) < EPS; } bool operator != (const TPoint& a, const TPoint& b) { return fabs(a.x - b.x) > EPS || fabs(a.y - b.y) > EPS; } TPoint operator - (const TPoint& a, const TPoint& b) { return TPoint(a.x - b.x, a.y - b.y); } TPoint operator + (const TPoint& a, const TPoint& b) { return TPoint(a.x + b.x, a.y + b.y); } double cross(const TPoint& a, const TPoint &b) { return a.x * b.y - a.y * b.x; } double cross(const TPoint& a, const TPoint &b, const TPoint &c) { return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y); } struct TLine { double a, b, c; bool lie(TPoint p) { return fabs(a*p.x + b*p.y + c) < EPS; } }; TLine get_line(TPoint& p1, TPoint& p2) { TLine tl; tl.a = p2.y - p1.y; tl.b = p1.x - p2.x; tl.c = p1.y*p2.x - p1.x*p2.y; if(tl.a < 0) tl.a*=-1.0, tl.b*=-1.0, tl.c*=-1.0; return tl; } struct TSegment { TPoint s, e; }ts[MAXN]; int same_side(TPoint &a, TPoint &b, TPoint& c, TPoint &d) { return sign(cross(a,b,c)) * sign(cross(a,b,d)); } bool same_side(TPoint &p1, TPoint &p2, TLine line) { return (line.a*p1.x+line.b*p1.y+line.c)*(line.a * p2.x + line.b * p2.y + line.c) > 0; } int main() { //freopen("input.txt", "r", stdin); int T; double x1, y1, x2, y2; sf(T); while(T--) { sf(n); int tot = 0; for(int i = 0; i < n; i++) { sfd(x1); sfd(y1); sfd(x2); sfd(y2); tp[tot++] = TPoint(x1, y1); tp[tot++] = TPoint(x2, y2); ts[i].s = TPoint(x1, y1); ts[i].e = TPoint(x2, y2); } bool ok = false; for(int i = 0; i < tot; i++) { for(int j = i + 1; j < tot; j++) { if(tp[i] == tp[j]) continue; TLine line = get_line(tp[i], tp[j]); bool flag = true; for(int k = 0; k < n; k++) { if(same_side(ts[k].e, ts[k].s, line)) { if(line.lie(ts[k].e) || line.lie(ts[k].s))continue; flag = false; break; } } if(flag) { ok = true; break; } } if(ok) break; } printf("%s\n", ok? "Yes!" : "No!"); } return 0; }HDU 1269 判断直线平行、重合、相交
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #define EPS 1e-6 #define sf(a) scanf("%d", &a) #define sfd(a) scanf("%lf", &a) using namespace std; struct TPoint { double x, y; TPoint() {} TPoint(int _x, int _y):x(_x), y(_y) {} }; struct TLine { double a, b, c; bool lie(TPoint p1) { return (a*p1.x + b*p1.y + c) < EPS; } }; TLine get_line(TPoint p1, TPoint p2) { TLine tl; tl.a = p2.y - p1.y; tl.b = p1.x - p2.x; tl.c = p1.y * p2.x - p1.x * p2.y; if(tl.a < 0) tl.a *= -1.0, tl.b *= -1.0, tl.c *= -1.0; return tl; } bool line_para(TLine l1, TLine l2) { return fabs(l1.a * l2.b - l1.b * l2.a) < EPS; } TPoint line_intersect(TLine l1, TLine l2) { TPoint tmp; if(l1.b == 0) { tmp.x = -l1.c / (double)l1.a; tmp.y = (-l2.c - l2.a * tmp.x) / (double)l2.b; } else { tmp.x = (double)(l1.c * l2.b - l1.b * l2.c) / (double)(l1.b*l2.a-l2.b*l1.a); tmp.y = (double)(-l1.c-l1.a*tmp.x)/(double)l1.b; } return tmp; } int main() { freopen("input.txt", "r", stdin); double x1, y1, x2, y2, x3, y3, x4, y4; TLine l1, l2; int n; sf(n); printf("INTERSECTING LINES OUTPUT\n"); while(n--) { sfd(x1); sfd(y1); sfd(x2); sfd(y2); sfd(x3); sfd(y3); sfd(x4); sfd(y4); l1 = get_line(TPoint(x1, y1), TPoint(x2, y2)); l2 = get_line(TPoint(x3, y3), TPoint(x4, y4)); if(line_para(l1, l2)) { if(l1.lie(TPoint(x3, y3)) && l2.lie(TPoint(x2, y2))) { printf("LINE\n"); } else { printf("NONE\n"); } } else { TPoint p = line_intersect(l1, l2); printf("POINT %.2f %.2f\n", p.x, p.y); } } printf("END OF OUTPUT\n"); return 0; }POJ 1410 判断线段是否在矩形内或者相交（可以直接看直线与矩形4线段是否相交）
（题目有坑，矩形给的点并不是如题所述的有序）
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<set> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sfd(a) scanf("%lf", &a) #define PI 3.14159265358979323 #define EPS 1e-6 using namespace std; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1 : 0); } struct TPoint { double x, y; TPoint() {} TPoint(const double& _x, const double& _y): x(_x), y(_y) {} }; bool operator == (const TPoint& a, const TPoint& b) { return fabs(a.x - b.x) < EPS && fabs(a.y - b.y) < EPS; } bool operator != (const TPoint& a, const TPoint& b) { return fabs(a.x - b.x) > EPS || fabs(a.y - b.y) > EPS; } TPoint operator - (const TPoint& a, const TPoint& b) { return TPoint(a.x - b.x, a.y - b.y); } TPoint operator + (const TPoint& a, const TPoint& b) { return TPoint(a.x + b.x, a.y + b.y); } double cross(const TPoint& a, const TPoint &b) { return a.x * b.y - a.y * b.x; } double cross(const TPoint& a, const TPoint &b, const TPoint &c) { return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y); } struct TSegment { TPoint s, e; }ts[5]; bool seg_inter(TSegment s1, TSegment s2) { TPoint a = s1.s, b = s1.e, c = s2.s, d = s2.e; return max(a.x, b.x) >= min(c.x, d.x) && max(c.x, d.x) >= min(a.x, b.x) && max(a.y, b.y) >= min(c.y, d.y) && max(c.y, d.y) >= min(a.y, b.y) && cross(a, b, c) * cross(a, b, d) <= EPS && cross(c, d, a) * cross(c, d, b) <= EPS; } int main() { freopen("input.txt", "r", stdin); int T; double x1, y1, x2, y2, x3, y3, x4, y4; sf(T); while(T--) { sfd(x1); sfd(y1); sfd(x2); sfd(y2); ts[0].s = TPoint(x1, y1); ts[0].e = TPoint(x2, y2); sfd(x3); sfd(y3); sfd(x4); sfd(y4); if(x3 > x4) swap(x3, x4); if(y3 < y4) swap(y3, y4); ts[1].s = TPoint(x3, y3); ts[1].e = TPoint(x3, y4); ts[2].s = TPoint(x4, y3); ts[2].e = TPoint(x4, y4); ts[3].s = TPoint(x3, y3); ts[3].e = TPoint(x4, y3); ts[4].s = TPoint(x3, y4); ts[4].e = TPoint(x4, y4); bool ok = (x1 >= x3 && x1 <= x4 && y1 <= y3 && y1 >= y4); if(!ok)for(int i = 1; i <= 4; i++) { ok = seg_inter(ts[0], ts[i]); if(ok)break; } puts(ok? "T" : "F"); } return 0; }POJ 1556 线段相交转化为最短路综合题
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<set> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sfd(a) scanf("%lf", &a) #define INF 0x3f3f3f3f #define PI 3.14159265358979323 #define EPS 1e-6 #define typec double using namespace std; const int MAXN = 100; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1 : 0); } struct TPoint { double x, y; TPoint() {} TPoint(const double& _x, const double& _y): x(_x), y(_y) {} }tp[MAXN]; double dist(const TPoint& a, const TPoint& b) { return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); } bool operator == (const TPoint& a, const TPoint& b) { return fabs(a.x - b.x) < EPS && fabs(a.y - b.y) < EPS; } bool operator != (const TPoint& a, const TPoint& b) { return fabs(a.x - b.x) > EPS || fabs(a.y - b.y) > EPS; } TPoint operator - (const TPoint& a, const TPoint& b) { return TPoint(a.x - b.x, a.y - b.y); } TPoint operator + (const TPoint& a, const TPoint& b) { return TPoint(a.x + b.x, a.y + b.y); } double cross(const TPoint& a, const TPoint &b) { return a.x * b.y - a.y * b.x; } double cross(const TPoint& a, const TPoint &b, const TPoint &c) { return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y); } struct TSegment { TPoint s, e; }ts[40]; bool seg_inter(TSegment s1, TPoint c, TPoint d) { TPoint a = s1.s, b = s1.e; return max(a.x, b.x) >= min(c.x, d.x) && max(c.x, d.x) >= min(a.x, b.x) && max(a.y, b.y) >= min(c.y, d.y) && max(c.y, d.y) >= min(a.y, b.y) && cross(a, b, c) * cross(a, b, d) <= EPS && cross(c, d, a) * cross(c, d, b) <= EPS; } typec cost[MAXN][MAXN]; typec lowcost[MAXN]; bool vis[MAXN]; int pre[MAXN]; void Dijkstra(int n, int beg) { for(int i = 0; i < n; i++) { lowcost[i] = INF; vis[i] = false; pre[i] = -1; } lowcost[beg] = 0; for(int j = 0; j < n; j++) { int k = -1; double Min = INF; for(int i = 0; i < n; i++) { if(!vis[i] && lowcost[i] < Min) { Min=lowcost[i]; k=i; } } if(k == -1)break; vis[k] = true; for(int i = 0; i < n; i++) { if(!vis[i] && lowcost[k] + cost[k][i] < lowcost[i]) { lowcost[i] = lowcost[k] + cost[k][i]; pre[i] = k; } } } } int main() { freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int n; while(sf(n) && n != -1) { tp[0] = TPoint(0, 5); tp[4*n+1] = TPoint(10, 5); for(int i = 0; i < n; i++) { sfd(tp[4*i+1].x); tp[4*i+2].x = tp[4*i+1].x; tp[4*i+3].x = tp[4*i+1].x; tp[4*i+4].x = tp[4*i+1].x; sfd(tp[4*i+1].y); sfd(tp[4*i+2].y); sfd(tp[4*i+3].y); sfd(tp[4*i+4].y); ts[2*i].s = tp[4*i+1]; ts[2*i].e = tp[4*i+2]; ts[2*i+1].s = tp[4*i+3]; ts[2*i+1].e = tp[4*i+4]; } int tot = 4*n+2; for(int i = 0; i < tot; i++) for(int j = 0; j < tot; j++) if(i == j)cost[i][j] = 0;else cost[i][j] = INF; for(int i = 0; i < tot; i++) { for(int j = i + 1; j < tot; j++) { if(tp[i].x == tp[j].x) continue; bool ok = true; for(int k = 0; k < n; k++) { if(ts[2*k].s.x > tp[i].x && ts[2*k].s.x < tp[j].x) { ok = seg_inter(ts[2*k], tp[i], tp[j]) || seg_inter(ts[2*k+1], tp[i], tp[j]); if(!ok)break; } } if(ok) { cost[i][j] = dist(tp[i], tp[j]); cost[j][i] = dist(tp[i], tp[j]); } } } if(cost[0][4*n+1] == 10) { printf("10.00\n"); } else { Dijkstra(tot, 0); printf("%.2f\n", lowcost[4*n+1]); } } return 0; }POJ 2653
这题的复杂度必然不少于O(mn)，剪枝非常重要，从当前往最后剪，因为10000里只有1000是好的，向上剪一点就很大概率被剪走，来回cover n^2次肯定是TLE的
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<set> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sfd(a) scanf("%lf", &a) #define INF 0x3f3f3f3f #define PI 3.14159265358979323 #define EPS 1e-6 #define typec double using namespace std; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1 : 0); } struct TPoint { double x, y; TPoint() {} TPoint(const double& _x, const double& _y): x(_x), y(_y) {} TPoint operator - (const TPoint& b)const { return TPoint(x - b.x, y - b.y); } double operator ^(const TPoint &b)const { return x*b.y - y*b.x; } }; struct TSegment { TPoint s, e; } ts[100005]; bool seg_inter(TPoint a, TPoint b, TPoint c, TPoint d) { return max(a.x, b.x) >= min(c.x, d.x) && max(c.x, d.x) >= min(a.x, b.x) && max(a.y, b.y) >= min(c.y, d.y) && max(c.y, d.y) >= min(a.y, b.y) && sign((c-a)^(b-a))*sign((d-a)^(b-a)) <= 0 && sign((a-c)^(d-c))*sign((b-c)^(d-c)) <= 0; } int ans[1001]; int main() { freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int n; while(sf(n) && n != 0) { int tot = 0; for(int i = 1; i <= n; i++) { sfd(ts[i].s.x); sfd(ts[i].s.y); sfd(ts[i].e.x); sfd(ts[i].e.y); } ans[tot++] = n; int now = n; while(--now > 0) { bool flag = true; for(int i = now + 1; i <= n; i++) { if(seg_inter(ts[now].s, ts[now].e, ts[i].s, ts[i].e)) { flag = false; break; } } if(flag)ans[tot++] = now; } printf("Top sticks: "); for(int i = tot-1; i > 0; i--) printf("%d, ", ans[i]); printf("%d.\n", ans[0]); } return 0; }HDU 1086 线段相交
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define INF 0x3f3f3f3f #define sfll(a) scanf("%lld", a) #define zero(x) (((x)>0?(x):-(x))<EPS) //#define __int64 long long typedef long long LL; using namespace std; const int MAXN = 105; struct TPoint { double x, y; TPoint(){} TPoint(const int& _x, const int& _y){x=_x; y = _y;} }; struct TSegment{ TPoint s, e; }; TSegment ts[MAXN]; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1 : 0); } double cross(const TPoint& a, const TPoint& b, const TPoint&c) { return (b.x - a.x) * (c.y-a.y) - (b.y - a.y) * (c.x - a.x); } bool seg_inter(TPoint & a, TPoint & b, TPoint & c, TPoint & d) { return max(a.x, b.x) >= min(c.x, d.x) && max(c.x, d.x) >= min(a.x, b.x) && max(a.y, b.y) >= min(c.y, d.y) && max(c.y, d.y) >= min(a.y, b.y) && cross(a, b, c) * cross(a, b, d) <= EPS && cross(c, d, a) * cross(c, d, b) <= EPS; } int main() { // freopen("input.txt", "r", stdin); //ios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int n; while(sf(n) && n != 0) { for(int i = 0; i < n; i++) { sfd(ts[i].s.x); sfd(ts[i].s.y); sfd(ts[i].e.x); sfd(ts[i].e.y); } int ans = 0; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(seg_inter(ts[i].s, ts[i].e, ts[j].s, ts[j].e)) ans++; } } printf("%d\n", ans); } return 0; } fzu 2110 线段组成锐角三角形判断 #include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define INF 0x3f3f3f3f #define sfll(a) scanf("%lld", a) #define zero(x) (((x)>0?(x):-(x))<EPS) //#define __int64 long long typedef long long LL; using namespace std; const int MAXN = 105; struct TPoint { double x, y; TPoint(){} TPoint(const int& _x, const int& _y){x=_x; y = _y;} }; TPoint tp[MAXN]; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1 : 0); } double dot(TPoint &a, TPoint& b, TPoint& c) { return (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y); } int main() { // freopen("input.txt", "r", stdin); //ios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int T; sf(T); while(T--) { int n; sf(n); for(int i = 0; i < n; i++) { sfd(tp[i].x); sfd(tp[i].y); } int ans = 0; for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) for(int k = j + 1; k < n; k++) { if(sign(dot(tp[i], tp[j], tp[k])) == 1 && sign(dot(tp[j], tp[i], tp[k])) == 1 && sign(dot(tp[k], tp[j], tp[i])) == 1) ans++; } printf("%d\n", ans); } return 0; } fzu 1393 三维空间四点共面问题 #include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define INF 0x3f3f3f3f #define sfll(a) scanf("%lld", a) #define zero(x) (((x)>0?(x):-(x))<EPS) //#define __int64 long long typedef long long LL; using namespace std; const int MAXN = 1500 + 5; struct point3 { double x, y, z; }; point3 xmult(point3 u, point3 v) { point3 ret; ret.x = u.y * v.z - v.y * u.z; ret.y = u.z * v.x - u.x * v.z; ret.z = u.x * v.y - u.y * v.x; return ret; } double dmult(point3 u, point3 v) { return u.x * v.x + u.y * v.y + u.z * v.z; } point3 subt(point3 u, point3 v) { point3 ret; ret.x = u.x-v.x; ret.y = u.y-v.y; ret.z = u.z-v.z; return ret; } point3 pvec(point3 s1, point3 s2, point3 s3) { return xmult(subt(s1, s2), subt(s2, s3)); } bool dots_onplane(point3 a, point3 b, point3 c, point3 d) { return zero(dmult(pvec(a, b, c), subt(d, a))); } int main() { // freopen("input.txt", "r", stdin); //ios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int T; sf(T); while(T--) { point3 a, b, c, d; sfd(a.x); sfd(a.y); sfd(a.z); sfd(b.x); sfd(b.y); sfd(b.z); sfd(c.x); sfd(c.y); sfd(c.z); sfd(d.x); sfd(d.y); sfd(d.z); if(dots_onplane(a, b, c, d)) puts("Yes"); else puts("No"); } return 0; }POJ 1696 贪心+角度排序
贪心就是必定能走完所有的点。
fzu模板上的角度模板是错的，这里自己改了以后AC了，说明模板改对了。
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define PI acos(-1.00) #define EPS 1e-6 #define INF 0x3f3f3f3f #define sfll(a) scanf("%lld", a) #define zero(x) (((x)>0?(x):-(x))<EPS) //#define __int64 long long typedef long long LL; using namespace std; const int MAXN = 50 + 5; struct TPoint { double x, y; int num; TPoint() {num = 0;} TPoint(const double& _x, const double& _y):x(_x), y(_y){num = 0;} TPoint operator-(const TPoint & b) const { return TPoint(x-b.x, y-b.y); } bool operator<(const TPoint &b) const { return num < b.num; } }; TPoint tp[MAXN]; double dot(const TPoint &a, const TPoint &b) { return a.x*b.x+a.y*b.y; } double cross(const TPoint &a, const TPoint &b) { return (a.x*b.y-a.y*b.x); } double cross(TPoint &a, TPoint &b, TPoint &c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } double len(const TPoint &a) { return sqrt((double)(a.x*a.x+a.y*a.y)); } double dis(const TPoint &a, const TPoint &b) { return len(a-b); } double angle(TPoint a, TPoint b) { double ret = acos(dot(a, b)/(len(a)*len(b))); if(cross(a, b)<0)return -ret + PI*2; return ret; } double angle(const TPoint& o, const TPoint&s, const TPoint&e) { return angle(s-o, e-o); } deque<int> Q; int main() { freopen("B.txt", "r", stdin); //ios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int T, intmp; sf(T); while(T--) { int n; sf(n); for(int i = 1; i <= n; i++) { sf(tp[i].num); sfd(tp[i].x); sfd(tp[i].y); } sort(tp+1, tp + n+1); int pb = 1; for(int i = 2; i <= n; i++) { if((tp[i].y == tp[pb].y && tp[i].x < tp[pb].x) || tp[i].y < tp[pb].y) pb = i; } Q.push_back(tp[pb].num); tp[pb].num = 0; TPoint last = TPoint(1, 0); while(Q.size() < n) { pb = 0; double now, p; for(int i = 1; i <= n; i++) { if(tp[i].num != 0) { if(pb == 0) { pb = i; now = angle(last, tp[i] - tp[Q.back()]); } else { p = angle(last, tp[i] - tp[Q.back()]); // printf("%f, %f %f %f\n", tp[i].x, tp[i].y, p, now); if(p < now) { pb = i; now = p; } } } } last = tp[pb] - tp[Q.back()]; Q.push_back(tp[pb].num); tp[pb].num = 0; } printf("%d", n); while(!Q.empty()) { printf(" %d", Q.front()); Q.pop_front(); } printf("\n"); } //printf("%f\n", angle(TPoint(-1, 1), TPoint(-1, -1.7324))*180/PI); return 0; }POJ 1066 贪心+线段相交
只要足够贪，什么都能简单化
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a) //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 30 + 5; struct TPoint { double x, y; TPoint(double _x = 0, double _y = 0):x(_x), y(_y){} bool operator != (const TPoint &b) const { if(fabs(x - b.x) <= EPS && fabs(y - b.y) <= EPS) return false; else return true; } }; TPoint tp[1000]; double cross(const TPoint &a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } struct TSegment { TPoint s, e; }; TSegment ts[MAXN]; bool seg_inter(TPoint &a, TPoint &b, TPoint &c, TPoint &d) { return max(a.x, b.x) >= min(c.x, d.x) && max(c.x, d.x) >= min(a.x, b.x) && max(a.y, b.y) >= min(c.y, d.y) && max(c.y, d.y) >= min(a.y, b.y) && cross(a, b, c) * cross(a, b, d) <= EPS && cross(c, d, a) * cross(c, d, b) <= EPS; } int main() { freopen("B.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int n; sf(n); int tot = 4; tp[0] = TPoint(0, 0); tp[1] = TPoint(0, 100); tp[2] = TPoint(100, 0); tp[3] = TPoint(100, 100); for(int i = 0; i < n; i++) { sfd(ts[i].s.x); sfd(ts[i].s.y); sfd(ts[i].e.x); sfd(ts[i].e.y); tp[tot++] = ts[i].s; tp[tot++] = ts[i].e; } TPoint ed; sfd(ed.x); sfd(ed.y); int ans = 999; for(int i = 0; i < tot; i++) { int cot = 0; for(int j = 0; j < n; j++) if(ts[j].s != tp[i] && ts[j].e != tp[i] && seg_inter(tp[i], ed, ts[j].s, ts[j].e)) cot++; //cout << cot << ' ' << tp[i].x << ' ' << tp[i].y << endl; if(cot < ans) ans = cot; } printf("Number of doors = %d\n", ans + 1); return 0; }POJ 3347 活生生一道没用到模板的几何题……通过数学计算转化为区间问题
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a)ŝ //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 50 + 5; int a[MAXN], b[MAXN]; int ans[MAXN], tot; int main() { freopen("B.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int n; while(sf(n) && n != 0) { for(int i = 1; i <= n; i++) { sf(a[i]); a[i] <<= 1; b[i] = 0; for(int j = 1; j < i; j++) { if(a[i] > a[j]) b[i] = max(b[i], b[j] + 3*a[j]/2 - a[i]/2); else b[i] = max(b[i], b[j] + a[j]/2 + a[i]/2); } } tot = 0; for(int i = 1; i <= n; i++) { int l = b[i], r = b[i] + a[i]; for(int j = 1; j < i; j++) { if(b[j] + a[j] > l) { l = b[j] + a[j]; } } for(int j = i + 1; j <= n; j++) { if(b[j] < r) { r = b[j]; } } if(l < r) ans[tot++] = i; } for(int i = 0; i < tot; i++) printf("%d%c", ans[i], i == tot-1? '\n' : ' '); } return 0; }FZU 1382 空间三角形的外接圆和内切圆
（如果不用坐标，直接用边长）
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define MOD 1000000007 #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a) //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 10000 + 5; double dist(double x1, double y1, double z1, double x2, double y2, double z2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2)); } int main() { freopen("input.txt", "r", stdin); //ios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); double x[3], y[3], z[3], a[3]; while(true) { for(int i = 0; i < 3; i++) { if(sfd(x[i]) == EOF) return 0; sfd(y[i]); sfd(z[i]); } for(int i = 0; i < 3; i++) a[i] = dist(x[i], y[i], z[i], x[(i+1) % 3], y[(i+1) % 3], z[(i+1) % 3]); double p = a[0] + a[1] + a[2]; p /= 2; double s = sqrt(p*(p-a[0])*(p-a[1])*(p-a[2])); double r1 = 2*s/(a[0]+a[1]+a[2]); double r2 = a[0]*a[1]*a[2]/s/4; printf("%.3f\n", r1*r1/r2/r2); } return 0; }POJ 2007 凸多边形斜率计算
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define PI acos(-1.00) #define EPS 1e-6 #define INF 0x3f3f3f3f #define sfll(a) scanf("%lld", a) #define zero(x) (((x)>0?(x):-(x))<EPS) //#define __int64 long long typedef long long LL; using namespace std; const int MAXN = 50 + 5; struct TPoint { int x, y; TPoint() {} TPoint(const int& _x, const int& _y):x(_x), y(_y){} TPoint operator-(const TPoint & b) const { return TPoint(x-b.x, y-b.y); } bool operator < (const TPoint& b) const { return ((double)y/x) < ((double)b.y/b.x); } }; int main() { freopen("input.txt", "r", stdin); //ios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); TPoint tp[4][MAXN]; int x, y; int tot = 0; int ok[4]; clr(ok, 0); while(cin >> x >> y) { if(x > 0 && y > 0) tp[0][ok[0]].x = x, tp[0][ok[0]++].y = y; if(x < 0 && y > 0) tp[1][ok[1]].x = x, tp[1][ok[1]++].y = y; if(x < 0 && y < 0) tp[2][ok[2]].x = x, tp[2][ok[2]++].y = y; if(x > 0 && y < 0) tp[3][ok[3]].x = x, tp[3][ok[3]++].y = y; } cout << "(0,0)\n"; int po = 0; for(int i = 0; i < 4; i++) sort(tp[i], tp[i] + ok[i]); bool pq = true; while(true) { if(pq && ok[po % 4]) { po++; continue; } pq = false; if(ok[po%4]) { for(;ok[po%4];po++) { for(int i = 0; i < ok[po%4]; i++) { cout << "(" << tp[po%4][i].x << "," << tp[po%4][i].y << ")" << endl; } } return 0; } po++; } return 0; }POJ 2826
出题人爆炸，网上的题解全是WA，做个鸡脖
然后有人说选C++，不要选G++，然后我就AC了，POJ爆炸
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define PI acos(-1.00) #define EPS 1e-6 #define INF 0x3f3f3f3f #define sfll(a) scanf("%lld", a) #define zero(x) (((x)>0?(x):-(x))<EPS) //#define __int64 long long typedef long long LL; using namespace std; const int MAXN = 50 + 5; struct TPoint { double x, y; TPoint() {} TPoint(const double& _x, const double& _y):x(_x), y(_y){} }; struct TLine { double a, b, c; }; TLine get_line(TPoint p1, TPoint p2) { TLine tl; tl.a = p2.y - p1.y; tl.b = p1.x - p2.x; tl.c = p1.y*p2.x-p1.x*p2.y; if(tl.a < 0) tl.a*=-1.0,tl.b*=-1.0,tl.c*=-1.0; //cout << tl.a << tl.b << tl.c << endl; return tl; } TPoint line_inter(TLine l1, TLine l2) { TPoint tmp; if(l1.b == 0) { tmp.x = -l1.c/(double)l1.a; tmp.y = (-l2.c-l2.a*tmp.x) / (double)l2.b; } else { tmp.x= (double)(l1.c*l2.b-l1.b*l2.c)/(double)(l1.b*l2.a-l2.b*l1.a); tmp.y= (double)(-l1.c-l1.a*tmp.x)/(double)l1.b; } return tmp; } int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1 : 0); } double cross(const TPoint& a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y) * (c.x-a.x); } bool on_seg(TPoint &c, TPoint &a, TPoint &b) { return (fabs(cross(c, a, b)) < EPS) && (c.x-a.x)*(c.x-b.x) < EPS && (c.y-a.y)*(c.y-b.y) < EPS; } double tri_area(TPoint &a, TPoint &b, TPoint &c) { return fabs(cross(a, b, c)) / 2.0; } bool para(TLine l1, TLine l2) { return fabs(l1.a*l2.b-l1.b*l2.a) < EPS; } int main() { // freopen("input.txt", "r", stdin); //ios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int T; sf(T); TPoint a, b, c, d, e, f; while(T--) { sfd(a.x); sfd(a.y); sfd(b.x); sfd(b.y); sfd(c.x); sfd(c.y); sfd(d.x); sfd(d.y); TLine ta = get_line(a, b); TLine tc = get_line(c, d); if(para(ta, tc)) { printf("0.00\n"); continue; } e = line_inter(ta, tc); //cout << e.x<<' '<< e.y << endl; if((!on_seg(e, a, b)) || (!on_seg(e, c, d)) || fabs(ta.a) <= EPS || fabs(tc.a) <= EPS) { printf("0.00\n"); continue; } if(a.y < b.y) { f = a; a = b; b = f; } if(c.y < d.y) { f = c; c = d; d = f; } if(sign(a.y - c.y)==0) { printf("%.2f\n", tri_area(e, c, a)); } else if(sign(a.y - c.y)==-1) { TLine l1; l1.a = 1; l1.b = 0; l1.c = -a.x; f = line_inter(l1, get_line(c, d)); if(on_seg(f, c, d) && sign(f.y - a.y) == 1) { printf("0.00\n"); continue; } TLine tmp; tmp.a = 0; tmp.b = 1; tmp.c = -a.y; f = line_inter(tmp, get_line(c, d)); printf("%.2f\n", tri_area(e, f, a)); } else { TLine l1; l1.a = 1; l1.b = 0; l1.c = -c.x; f = line_inter(l1, get_line(a, b)); if(on_seg(f, a, b) && sign(f.y - c.y) == 1) { printf("0.00\n"); continue; } TLine tmp; tmp.a = 0; tmp.b = 1; tmp.c = -c.y; f = line_inter(tmp, get_line(a, b)); printf("%.2f\n", tri_area(e, f, c)); } } //e = line_inter(get_line(TPoint(0, 0), TPoint(1, -1)), get_line(TPoint(1, -1), TPoint(2, 0))); //cout << e.x<<' '<< e.y << endl; return 0; }POJ 1039 折线管道中直线能走多远
注意double中ans初始化为最小不是0,应该是负无穷！
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a)ŝ //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 20 + 5; struct TPoint { double x, y; TPoint(){} TPoint(const double &_x, const double &_y):x(_x), y(_y) {} TPoint operator - (const TPoint &b) const { return TPoint(x - b.x, y - b.y); } }; TPoint tp[2][MAXN]; double len(const TPoint &a) { return sqrt((double)(a.x*a.x+a.y*a.y)); } double dis(const TPoint &a, const TPoint &b) { return len(b-a); } struct TLine { double a, b, c; double get_y(const double &x) { return (-c-a*x)/b; } }; TLine get_line(TPoint &p1, TPoint &p2) { TLine tl; tl.a = p2.y - p1.y; tl.b = p1.x - p2.x; tl.c = p1.y*p2.x-p1.x*p2.y; if(tl.a < 0) tl.a *= -1.0, tl.b *= -1.0, tl.c *= -1.0; return tl; } TPoint line_inter(TLine l1, TLine l2) { TPoint tmp; if(l1.b == 0) { tmp.x = -l1.c / (double)(l1.a); tmp.y = (-l2.c-l2.a*tmp.x)/(double)l2.b; } else { tmp.x = (double)(l1.c*l2.b-l1.b*l2.c)/(double)(l1.b*l2.a-l2.b*l1.a); tmp.y = (double)(-l1.c-l1.a*tmp.x)/(double)l1.b; } return tmp; } int main() { freopen("B.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int n; while(sf(n) && n != 0) { for(int i = 0; i < n; i++) { sfd(tp[0][i].x); sfd(tp[0][i].y); tp[1][i].x = tp[0][i].x; tp[1][i].y = tp[0][i].y - 1; } double ans = 0.0; bool ok = false; for(int i = 0; i < 2*n; i++) { int pz = i/2, pc = i%2; for(int j = 0; j < 2*n; j++) { int qz = j/2, qc = j%2; if(pz == qz)continue; bool flag = true; TLine tl = get_line(tp[pc][pz], tp[qc][qz]); for(int k = 0; k < n; k++) { if(k == qz || k == pz) continue; TPoint tmp = line_inter(tl, get_line(tp[0][k], tp[1][k])); if(tmp.y > tp[0][k].y || tmp.y < tp[1][k].y) { flag = false; break; } } if(flag) { ok = true; break; } } if(ok) break; } if(ok) { printf("Through all the pipe.\n"); } else { int l = 1; for(;l < n; l++) { ok = false; for(int i = 0; i <= 2*l+1; i++) { int pz = i/2, pc = i%2; for(int j = 0; j <= 2*l+1; j++) { int qz = j/2, qc = j%2; if(qz == pz)continue; bool flag = true; TLine tl = get_line(tp[pc][pz], tp[qc][qz]); for(int k = 0; k <= l; k++) { if(k == qz || k == pz) continue; TPoint tmp = line_inter(tl, get_line(tp[0][k], tp[1][k])); if(tmp.y > tp[0][k].y || tmp.y < tp[1][k].y) { flag = false; break; } } if(flag) { ok = true; break; } } if(ok)break; } if(!ok)break; } l--; double ans = tp[0][0].x; for(int i = 0; i <= 2*l+1; i++) { int pz = i / 2, pc = i%2; for(int j = 0; j <= 2*l+1; j++) { int qz = j/2, qc = j%2; if(pz == qz)continue; bool flag = true; TLine tl = get_line(tp[pc][pz], tp[qc][qz]); for(int k = 0; k <= l; k++) { if(k == qz || k == pz) continue; TPoint tmp = line_inter(tl, get_line(tp[0][k], tp[1][k])); if(tmp.y > tp[0][k].y || tmp.y < tp[1][k].y) { flag = false; break; } } if(flag) { TPoint tmp = line_inter(tl, get_line(tp[0][l], tp[0][l+1])); if(tmp.x >= tp[0][l].x && tmp.x <= tp[0][l+1].x && tmp.x > ans) ans = tmp.x; tmp = line_inter(tl, get_line(tp[1][l], tp[1][l+1])); if(tmp.x >= tp[1][l].x && tmp.x <= tp[1][l+1].x && tmp.x > ans) ans = tmp.x; } } if(ok)break; } printf("%.2f\n", ans); } } return 0; }POJ 3449 判断n边形相交
并不是一定存在某个点在另一个多边形内部或者边上，只能从边相交判断。
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a)ŝ //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 24 + 5; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1:0); } struct TPoint { double x, y; TPoint(){} TPoint(const double &_x, const double &_y):x(_x), y(_y) {} TPoint operator - (const TPoint &b) const { return TPoint(x - b.x, y - b.y); } }; struct TPolygon { TPoint p[MAXN]; int n; }; TPolygon tpo[MAXN]; double cross(const TPoint &a, const TPoint &b) { return (a.x * b.y - a.y * b.x); } double cross(const TPoint &a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } bool seg_inter(TPoint &a, TPoint &b, TPoint &c, TPoint &d) { return max(a.x, b.x) >= min(c.x, d.x) && max(c.x, d.x) >= min(a.x, b.x) && max(a.y, b.y) >= min(c.y, d.y) && max(c.y, d.y) >= min(a.y, b.y) && cross(a, b, c) * cross(a, b, d) <= EPS && cross(c, d, a) * cross(c, d, b) <= EPS; } int get_quadran(const TPoint &p) { return sign(p.x) >= 0 ? (sign(p.y) >= 0 ? 0 : 3) : (sign(p.y) >= 0 ? 1 : 2); } int point_int_poly(TPoint &t, TPoint q[], int n) { TPoint p[MAXN]; q[n] = q[0]; for(int i = 0; i <= n; i++) p[i] = q[i] - t; int t1 = get_quadran(p[0]); int sum = 0; for(int i = 1; i <= n; i++) { if(sign(p[i].x) == 0 && sign(p[i].y) == 0) return 2; int f = sign(cross(p[i-1], p[i])); if(f == 0 && sign(p[i-1].x*p[i].x) <= 0 && sign(p[i-1].y*p[i].y) <= 0) return 2; int t2 = get_quadran(p[i]); if(t2 == (t1+1)%4) sum++; else if(t2 == (t1+3) % 4) sum--; else if(t2 == (t1+2) % 4){ if(f > 0) sum += 2; else sum -= 2; } t1 = t2; } return sum != 0; } char str[MAXN]; char note[MAXN]; set<char> S[MAXN]; int main() { freopen("B.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); char ch, zc; int num, tot; while(true) { tot = 0; ch = getchar(); if(ch == '.') break; while(ch != '-') { note[tot] = ch; getchar(); zc = getchar(); while((ch = getchar()) != ' '); if(zc == 's') { tpo[tot].n = 4; scanf("(%lf,%lf)", &tpo[tot].p[0].x, &tpo[tot].p[0].y); getchar(); scanf("(%lf,%lf)", &tpo[tot].p[2].x, &tpo[tot].p[2].y); getchar(); tpo[tot].p[1].x = (tpo[tot].p[0].x + tpo[tot].p[0].y + tpo[tot].p[2].x - tpo[tot].p[2].y) / 2; tpo[tot].p[1].y = (-tpo[tot].p[0].x + tpo[tot].p[0].y + tpo[tot].p[2].x + tpo[tot].p[2].y) / 2; tpo[tot].p[3].x = (tpo[tot].p[0].x - tpo[tot].p[0].y + tpo[tot].p[2].x + tpo[tot].p[2].y) / 2; tpo[tot].p[3].y = (tpo[tot].p[0].x + tpo[tot].p[0].y - tpo[tot].p[2].x + tpo[tot].p[2].y) / 2; } else if(zc == 'r') { tpo[tot].n = 4; for(int i = 0; i < 3; i++) { scanf("(%lf,%lf)", &tpo[tot].p[i].x, &tpo[tot].p[i].y); getchar(); } tpo[tot].p[3].x = tpo[tot].p[0].x - tpo[tot].p[1].x + tpo[tot].p[2].x; tpo[tot].p[3].y = tpo[tot].p[0].y - tpo[tot].p[1].y + tpo[tot].p[2].y; } else { switch(zc) { case 'l' : tpo[tot].n = 2;break; case 't' : tpo[tot].n = 3;break; case 'p' : sfgc(tpo[tot].n);break; } for(int i = 0; i < tpo[tot].n; i++) { scanf("(%lf,%lf)", &tpo[tot].p[i].x, &tpo[tot].p[i].y); getchar(); } } ch = getchar(); tot++; } getchar(); for(int i = 0; i < tot; i++) { for(int j = i + 1; j < tot; j++) { for(int k = 0; k < tpo[i].n; k++) { bool ok = false; for(int m = 0; m < tpo[j].n; m++) { if(seg_inter(tpo[i].p[k], tpo[i].p[(k+1)%tpo[i].n], tpo[j].p[m], tpo[j].p[(m+1)%tpo[j].n])) { S[i].insert(note[j]); S[j].insert(note[i]); ok = true; break; } } if(ok)break; } } } for(int i = 'A'; i <= 'Z'; i++) { for(int j = 0; j < tot; j++) { if(note[j] == i) { int len = S[j].size(); if(len == 0) printf("%c has no intersections\n", i); else { set<char>::iterator it = S[j].begin(); for(int i = 0; i < len; i++, it++) { str[i] = *it; } if(len == 1) printf("%c intersects with %c\n", i, str[0]); else if(len == 2) printf("%c intersects with %c and %c\n", i, str[0], str[1]); else { printf("%c intersects with ", i); for(int k = 0; k < len - 1; k++) printf("%c, ", str[k]); printf("and %c\n", str[len - 1]); } S[j].clear(); } } } } printf("\n"); } return 0; }POJ 1584
圆在多边形内：1.圆心必须在多边形内2.到每条边所在直线的距离不能超过半径
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a)ŝ //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 100 + 5; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1:0); } struct TPoint { double x, y; TPoint(){} TPoint(const double &_x, const double &_y):x(_x), y(_y) {} TPoint operator - (const TPoint &b) const { return TPoint(x - b.x, y - b.y); } }; struct TSegment { TPoint s, e; }; struct TPolygon { TPoint p[MAXN]; int n; }; double dot(const TPoint &a, const TPoint &b) { return a.x*b.x+a.y*b.y; } double dot(const TPoint &a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y); } double cross(const TPoint &a, const TPoint &b) { return (a.x * b.y - a.y * b.x); } double cross(const TPoint &a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } int is_convex_poly(int n, TPoint p[]) { int t0 = sign(cross(p[n-1], p[0], p[1])); for(int i = 0; i <= n; i++) { int t1 = sign(cross(p[i%n], p[(i+1)%n], p[(i+2)%n])); if(t1*t0<0)return 0; // if(t1*t0==0)return 2; } return 1; } double len(const TPoint &a) { return sqrt((double)(a.x*a.x+a.y*a.y)); } double dis(const TPoint &a, const TPoint &b) { return len(a-b); } double relation(const TPoint &p, const TSegment &seg) { return dot(seg.s, p, seg.e) / (dis(seg.s, seg.e) * dis(seg.s, seg.e)); } TPoint perp_seg_pnt(const TPoint &p, const TSegment &seg) { double r = relation(p, seg); TPoint ret; ret.x = seg.s.x + r * (seg.e.x - seg.s.x); ret.y = seg.s.y + r * (seg.e.y - seg.s.y); return ret; } double dis_p2_seg(const TPoint &p, const TSegment &seg, TPoint &ret) { double r = relation(p, seg); if(r < 0) ret = seg.s; else if(r > 1) ret = seg.e; else ret = perp_seg_pnt(p, seg); return dis(p, ret); } int get_guadrant(const TPoint &p) { return sign(p.x) >= 0 ? (sign(p.y) >= 0 ? 0:3) : (sign(p.y) >= 0 ? 1 : 2); } int point_in_poly(TPoint &t, TPoint q[], int n) { TPoint p[MAXN]; q[n] = q[0]; for(int i = 0; i <= n; i++) p[i] = q[i] - t; int t1 = get_guadrant(p[0]); int sum = 0; for(int i = 1; i <= n; i++){ if(sign(p[i].x) == 0 && sign(p[i].y) == 0) return 2; int f = sign(cross(p[i-1], p[i])); if(f == 0 && sign(p[i-1].x * p[i].x)<=0 && sign(p[i-1].y * p[i].y)<=0) return 2; int t2 = get_guadrant(p[i]); if(t2 == (t1 + 1) % 4) sum++; else if(t2 == (t1 + 3) % 4) sum--; else if(t2 == (t1 + 2) % 4) { if(f > 0) sum += 2; else sum -= 2; } t1 = t2; } return sum != 0; } int main() { freopen("B.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); TPolygon tpo; TPoint tp, ret; TSegment ts; double r; while(sf(tpo.n) && tpo.n >= 3) { sfd(r); sfd(tp.x); sfd(tp.y); for(int i = 0; i < tpo.n; i++) { sfd(tpo.p[i].x); sfd(tpo.p[i].y); } if(is_convex_poly(tpo.n, tpo.p) == 0) { puts("HOLE IS ILL-FORMED"); } else { bool ok = ((point_in_poly(tp, tpo.p, tpo.n)) == 1); //if(!ok) cout << '*' << endl; //cout << (point_in_poly(tp, tpo.p, tpo.n)) << endl; if(ok)for(int i = 0; i < tpo.n; i++) { ts.s = tpo.p[i]; ts.e = tpo.p[(i+1)%tpo.n]; ret = perp_seg_pnt(tp, ts); //dis_p2_seg(tp, ts, ret); //cout << dis(ret, tp) << ' ' << r << endl; if(dis(ret, tp) < r) { ok = false; break; } } puts(ok ? "PEG WILL FIT" : "PEG WILL NOT FIT"); } } return 0; }POJ 3348
简单求凸包并求面积
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a)ŝ //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 10000 + 5; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1:0); } struct TPoint { double x, y; TPoint(){} TPoint(const double &_x, const double &_y):x(_x), y(_y) {} TPoint operator - (const TPoint &b) const { return TPoint(x - b.x, y - b.y); } }; TPoint tp[MAXN], tu[MAXN]; struct TSegment { TPoint s, e; }; struct TPolygon { TPoint p[MAXN]; int n; }; double dot(const TPoint &a, const TPoint &b) { return a.x*b.x+a.y*b.y; } double dot(const TPoint &a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y); } double cross(const TPoint &a, const TPoint &b) { return (a.x * b.y - a.y * b.x); } double cross(const TPoint &a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } double len(const TPoint &a) { return sqrt((double)(a.x*a.x+a.y*a.y)); } double dis(const TPoint &a, const TPoint &b) { return len(a-b); } bool graham_cmp(const TPoint &b, const TPoint &c) { TPoint *p = tp; double tmp = cross(b, c, p[0]); if(tmp > EPS) return true; if(fabs(tmp) < EPS && (dis(b, p[0]) < dis(c, p[0]))) return true; return false; } int graham_scan(TPoint hull[], int n) { TPoint *p = tp; int top, k = 0; for(int i = 1; i < n; i++) if((p[k].y-p[i].y>EPS) || (fabs(p[i].y-p[k].y)<EPS && p[k].x-p[i].x>EPS)) k = i; swap(p[0], p[k]); sort(p+1,p+n,graham_cmp); hull[0] = p[0], hull[1] = p[1], hull[2] = p[2]; top = 3; for(int i = 3; i < n; i++) { while(top >= 2 && cross(hull[top-2], hull[top-1], p[i]) < EPS) --top; hull[top++] = p[i]; } return top; } double area_poly(TPoint p[], int n) { double res = 0; p[n] = p[0]; for(int i =0; i < n; i++) res += cross(p[i], p[i+1]); return fabs(res) / 2.00; } int main() { freopen("B.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int n; sf(n); for(int i = 0; i < n; i++) { sfd(tp[i].x); sfd(tp[i].y); } if(n < 3) puts("0"); else { int num = graham_scan(tu, n); double p = area_poly(tu, num); p /= 50.0; printf("%d\n", (int)p); } return 0; }FZU 1016
矩形包含另一矩形 模板P76
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a)ŝ //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 10000 + 5; bool zero(double a) { return fabs(a) < EPS; } bool r2inr1(double A, double B, double C, double D) { if(A < B) swap(A, B); if(C < D) swap(C, D); if(A > C && B > D) return true; if(C>A&&D<B&&(C*C-D*D)*sqrt(C*C+D*D-B*B)-A*(C*C+D*D)+2*C*D*B < 0) return true; return false; } int main() { freopen("B.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); while(true) { double a, b, x, y; sfd(a); sfd(b); sfd(x); sfd(y); if(zero(a)&&zero(b)&&zero(x)&&zero(y))break; if(r2inr1(a,b,x,y)) puts("Escape is possible."); else puts("Box cannot be dropped."); } return 0; }
fzu 1830 hdu 3011 四面体面积问题
注意！！！如果某条边为0,必须特殊对待
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a)ŝ //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 10000 + 5; double volume(double a, double b, double c, double al, double bl, double cl) { double aa = a*a, bb = b*b, cc = c*c; double m = bb+cc-al*al, n = aa+cc-bl*bl, p = aa+bb-cl*cl; double v = aa*bb*cc - ((aa*m*m)+(bb*n*n)+(cc*p*p)-m*n*p)/4.0; return sqrt(v)/6.0; } double arc60(double a, double b) { return sqrt(a*a+b*b-a*b); } int main() { freopen("B.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int n, e; while(sf2(n, e) != EOF) {//命名时顶点按字典序 double ab,ac,ad,bc,bd,cd; ab=ac=ad=bc=bd=cd=(double)n; double v = volume(ab,ac,ad,cd,bd,bc); double ce = (double)e; double df = ce; double be = bc - ce; double bf = be; double ef = be; double ae = arc60(ab,be); double af = ae; // cout << v<<endl<<2*volume(ab,ae,af,ef,bf,be)<<endl; if(2*volume(ab,ae,af,ef,bf,be) > v) { puts("Oh, my god!"); continue; } v /= 2.0; if(n == e) { printf("%.2f\n", n / 2.0 * sqrt(2)); continue; } double l = 0, r = (double)n; while(l < r - EPS) { double ag = (l + r) / 2; double cg = ac - ag; double eg = arc60(cg,ce); double dh = cg; double fh = arc60(df,dh); double gh = ag; double cf = arc60(df, cd); double dg = arc60(cg, cd); double fg = sqrt(eg*fh+gh*ef); double v1 = volume(gh, dh, fh, df, fg, dg); double v2 = volume(cg,dg,fg,df,cf,cd); double v3 = volume(cg,eg,fg,ef,cf,ce); if(v1 + v2 + v3 > v) l = ag; else r = ag; } printf("%.2f\n", l); } return 0; }hdu 4998
如果一个点旋转后是另一个点，那旋转中心一定在他的中垂线上，来两条这样不重合的中垂线即可。
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a)ŝ //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 10 + 5; int sign(double d) { return d > EPS? 1 : (d < -EPS? -1:0); } struct TPoint { double x, y; TPoint (){} TPoint (const double& _x, const double& _y) :x(_x),y(_y){} bool operator == (const TPoint &b) const { return sign(x-b.x) == 0 && sign(y-b.y) == 0; } TPoint operator - (const TPoint &b) const { return TPoint(x - b.x, y - b.y); } }; struct TLine { double a, b, c; }; TLine get_line(TPoint &p1, TPoint &p2) { TLine t1; t1.a = p2.y - p1.y; t1.b = p1.x - p2.x; t1.c = p1.y * p2.x - p1.x * p2.y; if(t1.a < 0) t1.a*=-1.0, t1.b*=-1.0, t1.c*=-1.0; return t1; } TLine prep_mid_seg(TPoint a, TPoint b) { TPoint s, e; s.x = (a.x + b.x) * 0.5; s.y = (a.y + b.y) * 0.5; e.x = s.x - (a.y - b.y); e.y = s.y + (a.x - b.x); return get_line(s, e); } bool line_para(TLine l1, TLine l2) { return fabs(l1.a * l2.b - l1.b * l2.a) < EPS; } int n; TPoint tp[MAXN]; double arc[MAXN]; TPoint tc[MAXN]; TPoint rot(TPoint &o, double alpha, TPoint p) { TPoint tmp; p.x -=o.x, p.y-=o.y; tmp.x = p.x * cos(alpha)-p.y * sin(alpha) + o.x; tmp.y = p.y * cos(alpha)+p.x * sin(alpha) + o.y; return tmp; } TPoint rop(TPoint p) { for(int i = 0; i < n; i++) p = rot(tp[i], arc[i], p); return p; } double len(const TPoint &a) { return sqrt(a.x * a.x + a.y * a.y); } double dot(const TPoint &a, const TPoint &b) { return a.x * b.x + a.y * b.y; } double cross(const TPoint &a, const TPoint &b) { return (a.x * b.y - a.y * b.x); } double angle(TPoint a, TPoint b) { double ret = acos(dot(a, b) / (len(a) * len(b))); if(cross(a, b) < 0) return 2*PI - ret; return ret; } double angle(TPoint o, TPoint s, TPoint e) { return angle(s-o, e-o); } TPoint line_intersect(TLine l1, TLine l2) { TPoint tmp; if(l1.b == 0) { tmp.x = -l1.c / (double) l1.a; tmp.y = (-l2.c - l2.a * tmp.x) / (double) l2.b; } else { tmp.x = (double)(l1.c*l2.b-l1.b*l2.c) / (double)(l1.b*l2.a-l2.b*l1.a); tmp.y = (double)(-l1.c-l1.a*tmp.x)/(double)l1.b; } return tmp; } int main() { freopen("B.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); tc[0] = TPoint(0.0,0.0); tc[1] = TPoint(1.0,1.0); tc[2] = TPoint(2.0,1.0); tc[3] = TPoint(0.0,2.0); tc[4] = TPoint(3.0,8.0); int T; sf(T); while(T--) { sf(n); for(int i = 0; i < n; i++) { sfd(tp[i].x); sfd(tp[i].y); sfd(arc[i]); } bool ok = false; for(int i = 0; i < 5; i++) { TPoint t1 = rop(tc[i]); if(!(t1 == tc[i])) for(int j = i + 1; j < 5; j++) { TPoint t2 = rop(tc[j]); if(!(t2 == tc[j])) { TLine l1 = prep_mid_seg(t1, tc[i]); TLine l2 = prep_mid_seg(t2, tc[j]); if(!line_para(l1, l2)) { TPoint tmp = line_intersect(l1, l2); double dd = angle(tmp, tc[i], t1); printf("%f %f %f\n", tmp.x, tmp.y, dd); ok = true; } } if(ok)break; } if(ok)break; } } return 0; }POJ 2187 最远顶点对
注意floor返回值为double，必须(int)
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a)ŝ //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 100000 + 5; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1:0); } struct TPoint { double x, y; TPoint(){} TPoint(const double &_x, const double &_y):x(_x), y(_y) {} TPoint operator - (const TPoint &b) const { return TPoint(x - b.x, y - b.y); } }; TPoint tp[MAXN], tu[MAXN]; struct TSegment { TPoint s, e; }; struct TPolygon { TPoint p[MAXN]; int n; }; double dot(const TPoint &a, const TPoint &b) { return a.x*b.x+a.y*b.y; } double dot(const TPoint &a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y); } double cross(const TPoint &a, const TPoint &b) { return (a.x * b.y - a.y * b.x); } double cross(const TPoint &a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } double len(const TPoint &a) { return sqrt((double)(a.x*a.x+a.y*a.y)); } double dis(const TPoint &a, const TPoint &b) { return len(a-b); } bool graham_cmp(const TPoint &b, const TPoint &c) { TPoint *p = tp; double tmp = cross(b, c, p[0]); if(tmp > EPS) return true; if(fabs(tmp) < EPS && (dis(b, p[0]) < dis(c, p[0]))) return true; return false; } int graham_scan(TPoint p[], TPoint hull[], int n) { int top, k = 0; for(int i = 1; i < n; i++) if((p[k].y-p[i].y>EPS) || (fabs(p[i].y-p[k].y)<EPS && p[k].x-p[i].x>EPS)) k = i; swap(p[0], p[k]); sort(p+1,p+n,graham_cmp); hull[0] = p[0], hull[1] = p[1], hull[2] = p[2]; top = 3; for(int i = 3; i < n; i++) { while(top >= 2 && cross(hull[top-2], hull[top-1], p[i]) < EPS) --top; hull[top++] = p[i]; } return top; } TPoint c[MAXN]; double longest_pair(TPoint p[], int n) { int i, j, k = 1, l = graham_scan(p, c, n); double d, maxt = 0.0; c[l] = c[0], c[l+1] = c[1]; while(k < l && sign(cross(c[0], c[1], c[k]) - cross(c[0], c[1], c[k+1])) < 0)k++; for(j = k, i = 0, k++; i < j || k < l; ){ if(sign(cross(c[i], c[i+1], c[k]) - cross(c[i], c[i+1], c[k+1])) < 0) k++; else i++; d = dis(c[i], c[k]); if(d > maxt) maxt = d; } return maxt; } int main() { // freopen("input.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); int n; sf(n); for(int i = 0; i < n; i++) { sfd(tp[i].x); sfd(tp[i].y); } double ans = longest_pair(tp, n); if(n < 6) { ans = 0.0; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { double p = dis(tp[i], tp[j]); if(p > ans) ans = p; } } } cout << (int)(ans*ans + 0.5) << endl; return 0; } HDU 2892 圆和多边形面积交
国内OJ默认EOF
#include<iostream> #include<algorithm> #include<iomanip> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<deque> #include<stack> #define clr(a, b) memset(a, b, sizeof(a)) #define sf(a) scanf("%d", &a) #define sf2(a, b) scanf("%d%d", &a, &b) #define sf3(a, b, c) scanf("%d%d%d", &a, &b, &c) #define sfd(a) scanf("%lf", &a) #define sfs(a) scanf("%s", a) #define sfgc(a) scanf("%d", &a);getchar() #define EPS 1e-6 #define PI acos(-1.00) #define INF 0x3f3f3f3f //#define __int64 long long //#define sfll(a) scanf("%lld", &a)ŝ //#define sfll(a) scanf("%I64d", &a) //typedef long long LL; using namespace std; const int MAXN = 100000 + 5; const double GRAND = 10.0; int sign(double d) { return d < -EPS ? -1 : (d > EPS ? 1:0); } struct TPoint { double x, y; TPoint(){} TPoint(const double &_x, const double &_y):x(_x), y(_y) {} TPoint operator - (const TPoint &b) const { return TPoint(x - b.x, y - b.y); } TPoint operator + (const TPoint &b) const { return TPoint(x + b.x, y + b.y); } }; TPoint tp[MAXN]; double dot(const TPoint &a, const TPoint &b) { return a.x*b.x+a.y*b.y; } double dot(const TPoint &a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y); } double cross(const TPoint &a, const TPoint &b) { return (a.x * b.y - a.y * b.x); } double cross(const TPoint &a, const TPoint &b, const TPoint &c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } double len(const TPoint &a) { return sqrt((double)(a.x*a.x+a.y*a.y)); } double dis(const TPoint &a, const TPoint &b) { return len(a-b); } double dist_sqr(const TPoint &a, const TPoint &b) { return (a.x - b.x)*(a.x-b.x) + (a.y - b.y) * (a.y-b.y); } double cal_sita(double a, double b, double c) { double ans = (a + b - c) / (2 * sqrt(a) * sqrt(b)); if(ans > 1) ans = 1; if(ans < -1) ans = -1; return acos(ans); } double sector(const double&r, const double &sita) { return 0.5*r*r*sita; } int find_cross_point(TPoint a, TPoint b, double r, TPoint &p1, TPoint &p2) { double leng = dis(a, b); double d = fabs(cross(a, b)) / leng; if(sign(d-r) >= 0) return 0; TPoint vec; if(cross(a, b, TPoint(0, 0)) < 0) vec = b-a; else vec = a-b; vec = TPoint(-vec.y, vec.x); vec.x *= d / leng; vec.y *= d / leng; TPoint add = b - a; double tmp = sqrt(r*r-d*d) / leng; add.x *= tmp; add.y *= tmp; TPoint tmp1 = vec + add; TPoint tmp2 = vec - add; if(dist_sqr(a, tmp1) > dist_sqr(a, tmp2)){ swap(tmp1, tmp2); } bool flag1 = (sign(dot(tmp1, a, b)) < 0); bool flag2 = (sign(dot(tmp2, a, b)) < 0); if(flag1 && flag2) { p1 = tmp1, p2 = tmp2; return 2; } if(flag1){ p1 = tmp1; return 1; } if(flag2) { p1 = tmp2; return 1; } return 0; } double commom_area(TPoint a, TPoint b, double r) { double lena = a.x*a.x+a.y*a.y, lenb = b.x*b.x+b.y*b.y; double rr = r*r; if(sign(lena-rr)<=0 && sign(lenb-rr) <= 0) { return fabs(0.5*cross(a, b)); } TPoint p1, p2; int cnt = find_cross_point(a, b, r, p1, p2); if(cnt == 0) { return sector(r, cal_sita(lena, lenb, dist_sqr(a, b))); } if(cnt == 1) { if(lena < lenb) { swap(a,b); swap(lena, lenb); } return sector(r, cal_sita(lena, rr, dist_sqr(a, p1))) + 0.5 * fabs(cross(p1, b)); } if(cnt == 2) { return fabs(0.5*cross(p1, p2)) + sector(r, cal_sita(lena, rr, dist_sqr(a, p1))) + sector(r, cal_sita(lenb, rr, dist_sqr(b, p2))); } return 0; } double poly_common_area(TPoint dt[], TPoint C, double r, int n) { double ans = 0; dt[n] = dt[0]; dt[0] = dt[0] - C; for(int i = 0; i < n; i++) { dt[i+1] = dt[i+1] - C; ans += commom_area(dt[i], dt[i+1], r) * sign(cross(dt[i], dt[i+1])); } return fabs(ans); } int main() { // freopen("input.txt", "r", stdin); //dios::sync_with_stdio(false); //freopen("output.txt", "w", stdout); TPoint mid; int n; double r, x, y, h, dx, dy; while(sfd(x) != EOF) { sfd(y); sfd(h); sfd(dx); sfd(dy); double t = sqrt(2*h/GRAND); mid.x = x + t*dx; mid.y = y + t*dy; sfd(r); sf(n); for(int i = 0; i < n; i++) { sfd(tp[i].x); sfd(tp[i].y); } printf("%.2f\n", poly_common_area(tp, mid, r, n)); } return 0; }FZU 2153 从凸包原理引申出的极角排序DP
#include <iostream> #include <algorithm> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <cmath> #include <stack> #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long int #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 1000000007 #define LM(a,b) (((ULL)(a))<<(b)) #define RM(a,b) (((ULL)(a))>>(b)) using namespace std; const double PI = acos(-1.0); struct P { double x,y,a; }p[1100],tp[1100]; int dp[51][51]; bool cmpxy(P p1,P p2) { return ( p1.y < p2.y || (fabs(p1.y-p2.y) < EPS && p1.x < p1.x ) ); } bool cmp_angle(P p1,P p2) { return (p1.a < p2.a || (fabs(p1.a-p2.a) < EPS && p1.y < p2.y) ||(fabs(p1.a-p2.a) < EPS && fabs(p1.y-p2.y) < EPS && p1.x < p2.x) ); } double X_Mul(P a1,P a2,P b1,P b2) { P v1 = {a2.x-a1.x,a2.y-a1.y},v2 = {b2.x-b1.x,b2.y-b1.y}; return v1.x*v2.y - v1.y*v2.x; } double Cal_Angle(P t,P p) { return ((t.x-p.x)*(t.x-p.x) + 1 - (t.x-p.x-1)*(t.x-p.x-1))/(2*sqrt((t.x-p.x)*(t.x-p.x) + (t.y-p.y)*(t.y-p.y))); } void Sort_By_Angle(P *p,int n) { P re = p[0]; p[0].a = -2; for(int i = 1;i < n; ++i) { p[i].a = Cal_Angle(re,p[i]); } sort(p,p+n,cmp_angle); } int Max; void Updata_Max(P *p,int n) { int i,j,k; for(i = 0;i < n; ++i) { tp[i] = p[i]; } Sort_By_Angle(tp,n); for(i = 1;i < n; ++i) { for(j = i+1;j < n; ++j) dp[i][j] = 3; } for(i = 1;i < n; ++i) { for(j = i+1;j < n; ++j) { for(k = j+1;k < n; ++k) { if(dp[i][j] >= dp[j][k] && X_Mul(tp[i],tp[j],tp[i],tp[k]) > 0) { dp[j][k] = dp[i][j]+1; Max = max(dp[j][k],Max); } } } } } int main() { int icase = 1,T,n,i; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i = 0;i < n; ++i) { scanf("%lf%lf",&p[i].x,&p[i].y); } sort(p,p+n,cmpxy); Max = 3; for(i = 0;i < n ; ++i) { if(n-i <= Max) break; Updata_Max(&p[i],n-i); } printf("Case#%d: %d\n",icase++,Max); } return 0; }
至此，计算几何专题完。
