L - Two Ants Gym - 102823L

題意：

有兩個線段A，B，兩個線段不會超過一個公共點，
你站在線段B上，整個平面你看不到的區域的面積(如圖中S所在區域)

題解：

計算幾何，惡心題。調了一個小時還是不對，吐了
基本思路：很明顯S所在區域是一個三角形，其中兩點是線段w的兩端，那我們求出第三個點即可
基本思路是正確的，但是本題要處理的細節很多：
如圖，此時面積為inf

如圖，此時面積為inf

如圖，此時面積為0.00

如圖，此時情況為inf

此時面積為紅色區域

情況非常多，總結下：
線段W退化成點，答案為0
線段B退化成點，答案為inf
兩線段規范相交，答案為0
兩線段非規范相交：
若有共線答案為0。
否則即交點在端點，答案為inf
兩線段不相交：
B線段的兩點在W線段的兩側，答案為0.
否則：
兩個線段端點彼此之間的連線，若有交點，判斷其相對位置，如果相對于W線段不與黑色線段同側，則計算該點與W線段構成的面積即是答案。
若沒有交點（平行），或者交點都在B線段同側，則答案為inf.

代碼：

AC代碼，代碼網上的，真的改不動了

#include<bits/stdc++.h> using namespace std;// `計算幾何模板` const double eps = 1e-14; const double inf = 1e20; const double pi = acos(-1.0); const int maxp = 1010; //`Compares a double to zero` int sgn(double x) {if (fabs(x) < eps) { return 0; }else { return x < 0 ? -1 : 1; } } //square of a double inline double sqr(double x) {return x * x;} struct Point {double x, y;Point() {}Point(double _x, double _y){x = _x;y = _y;}void input(){scanf("%lf%lf", &x, &y);}void output(){printf("%.2f %.2f\n", x, y);}bool operator == (Point b)const{return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;}bool operator < (Point b)const{return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;}Point operator -(const Point &b)const{return Point(x - b.x, y - b.y);}//叉積double operator ^(const Point &b)const{return x * b.y - y * b.x;}//點積double operator *(const Point &b)const{return x * b.x + y * b.y;}//返回長度double len(){return hypot(x, y); //庫函數}//返回長度的平方double len2(){return x * x + y * y;}//返回兩點的距離double distance(Point p){return hypot(x - p.x, y - p.y);}Point operator +(const Point &b)const{return Point(x + b.x, y + b.y);}Point operator *(const double &k)const{return Point(x * k, y * k);}Point operator /(const double &k)const{return Point(x / k, y / k);}//`計算pa 和 pb 的夾角`//`就是求這個點看a,b 所成的夾角`//`測試 LightOJ1203`double rad(Point a, Point b){Point p = *this;return fabs(atan2( fabs((a - p) ^ (b - p)), (a - p) * (b - p) ));}//`化為長度為r的向量`Point trunc(double r){double l = len();if (!sgn(l)) { return *this; }r /= l;return Point(x * r, y * r);}//`逆時針旋轉90度`Point rotleft(){return Point(-y, x);}//`順時針旋轉90度`Point rotright(){return Point(y, -x);}//`繞著p點逆時針旋轉angle`Point rotate(Point p, double angle){Point v = (*this) - p;double c = cos(angle), s = sin(angle);return Point(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);} }; struct Line {Point s, e;Line() {}Line(Point _s, Point _e){s = _s;e = _e;}bool operator ==(Line v){return (s == v.s) && (e == v.e);}//`根據一個點和傾斜角angle確定直線,0<=angle<pi`Line(Point p, double angle){s = p;if (sgn(angle - pi / 2) == 0) {e = (s + Point(0, 1));} else {e = (s + Point(1, tan(angle)));}}//ax+by+c=0Line(double a, double b, double c){if (sgn(a) == 0) {s = Point(0, -c / b);e = Point(1, -c / b);} else if (sgn(b) == 0) {s = Point(-c / a, 0);e = Point(-c / a, 1);} else {s = Point(0, -c / b);e = Point(1, (-c - a) / b);}}void input(){s.input();e.input();}void adjust(){if (e < s) { swap(s, e); }}//求線段長度double length(){return s.distance(e);}//`返回直線傾斜角 0<=angle<pi`double angle(){double k = atan2(e.y - s.y, e.x - s.x);if (sgn(k) < 0) { k += pi; }if (sgn(k - pi) == 0) { k -= pi; }return k;}//`點和直線關系`//`1 在左側`//`2 在右側`//`3 在直線上`int relation(Point p){int c = sgn((p - s) ^ (e - s));if (c < 0) { return 1; }else if (c > 0) { return 2; }else { return 3; }}// 點在線段上的判斷bool pointonseg(Point p){return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0;}//`兩向量平行(對應直線平行或重合)`bool parallel(Line v){return sgn((e - s) ^ (v.e-v.s)) == 0;}//`兩線段相交判斷`//`2 規范相交`//`1 非規范相交`//`0 不相交`int segcrossseg(Line v){int d1 = sgn((e - s) ^ (v.s - s));int d2 = sgn((e - s) ^ (v.e-s));int d3 = sgn((v.e-v.s) ^ (s - v.s));int d4 = sgn((v.e-v.s) ^ (e - v.s));if ( (d1 ^ d2) == -2 && (d3 ^ d4) == -2 ) { return 2; }return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||(d2 == 0 && sgn((v.e-s) * (v.e-e)) <= 0) ||(d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||(d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);}//`直線和線段相交判斷`//`-*this line -v seg`//`2 規范相交`//`1 非規范相交`//`0 不相交`int linecrossseg(Line v){int d1 = sgn((e - s) ^ (v.s - s));int d2 = sgn((e - s) ^ (v.e-s));if ((d1 ^ d2) == -2) { return 2; }return (d1 == 0 || d2 == 0);}//`兩直線關系`//`0 平行`//`1 重合`//`2 相交`int linecrossline(Line v){if ((*this).parallel(v)) {return v.relation(s) == 3;}return 2;}//`求兩直線的交點`//`要保證兩直線不平行或重合`Point crosspoint(Line v){double a1 = (v.e-v.s) ^ (s - v.s);double a2 = (v.e-v.s) ^ (e - v.s);return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));}//點到直線的距離double dispointtoline(Point p){return fabs((p - s) ^ (e - s)) / length();}//點到線段的距離double dispointtoseg(Point p){if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0) {return min(p.distance(s), p.distance(e));}return dispointtoline(p);}//`返回線段到線段的距離`//`前提是兩線段不相交，相交距離就是0了`double dissegtoseg(Line v){return min(min(dispointtoseg(v.s), dispointtoseg(v.e)), min(v.dispointtoseg(s), v.dispointtoseg(e)));}//`返回點p在直線上的投影`Point lineprog(Point p){Point v = e - s;return s + ( (v * (v * (p - s))) / (v.len2()) );}//`返回點p關于直線的對稱點`Point symmetrypoint(Point p){Point q = lineprog(p);return Point(2 * q.x - p.x, 2 * q.y - p.y);} };int main() {int T;cin >> T;Line w, b;int cas = 0;Line l1, l2, l3, l4;Point cp;int sg;double ans;while (T--) {++cas;w.input();b.input();if (w.s == w.e) {printf("Case %d: 0.000\n", cas);} else if (b.s == b.e) {printf("Case %d: inf\n", cas);} else {int crs = w.segcrossseg(b);if (crs == 2) {printf("Case %d: 0.000\n", cas);} else if (crs == 1) {if (w.relation(b.s) == 3 && w.relation(b.e) == 3) {printf("Case %d: 0.000\n", cas);} else if (w.pointonseg(b.s) || w.pointonseg(b.e)) {printf("Case %d: inf\n", cas);} else {printf("Case %d: 0.000\n", cas);}} else {if (sgn((w.e - w.s) ^ (b.e - w.s)) * sgn((w.e - w.s) ^ (b.s - w.s)) <= 0) {printf("Case %d: 0.000\n", cas);} else {sg = sgn((w.e - w.s) ^ (b.e - w.s));bool flag = false;l1 = Line(w.e, b.e);l2 = Line(w.s, b.s);l3 = Line(w.e, b.s);l4 = Line(w.s, b.e);if (!l1.parallel(l2)) {cp = l1.crosspoint(l2);if (sgn((w.e - w.s) ^ (cp - w.s)) != sg) {flag = true;ans = abs((w.e - w.s) ^ (cp - w.s)) / 2;}}if (!l3.parallel(l4)) {cp = l3.crosspoint(l4);if (sgn((w.e - w.s) ^ (cp - w.s)) != sg) {flag = true;ans = abs((w.e - w.s) ^ (cp - w.s)) / 2;}}if (!flag) {printf("Case %d: inf\n", cas);} else {printf("Case %d: %.10f\n", cas, ans);}}}}} }

總結

以上是生活随笔為你收集整理的L - Two Ants Gym - 102823L的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。