POJ 2826 An Easy Problem?! (计算几何)
程序员文章站
2022-04-02 10:06:38
...
题意:两根木棒,给出两者位置,求能接多少雨水。
题解:计算几何
太多注意的点了,以至于代码改了好多遍很乱。
说一下wa的点
①可能重合
②输出结果+eps
③没考虑如下情况
剩下的就是比较大小,叉积求面积。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
const double eps = 1e-8;
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;
if (x < 0) return -1;
else return 1;
}
//POINT
struct Point {
double x, y;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
}
Point operator -(const Point& b)const {
return Point(x - b.x, y - b.y);
}
//叉积
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;
}
};
//LINE
struct Line {
Point s, e;
Line() {}
Line(Point _s, Point _e) {
s = _s;
e = _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;
}
//两线段相交判断
//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);
}
//点和直线关系
//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 parallel(Line v) {
return sgn((e - s) ^ (v.e - v.s)) == 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));
}
};
int n;
double xa1, ya1, xb1, yb1, xa2, ya2, xb2, yb2, xl, yl, xr, yr;
int main() {
scanf("%d", &n);
while (n--) {
scanf("%lf%lf%lf%lf", &xa1, &ya1, &xb1, &yb1);
Line a = Line(Point(xa1, ya1), Point(xb1, yb1));
scanf("%lf%lf%lf%lf", &xa2, &ya2, &xb2, &yb2);
Line b = Line(Point(xa2, ya2), Point(xb2, yb2));
if (a.segcrossseg(b) == 0 || a.linecrossline(b) == 1) puts("0.00");
else {
if (a.angle() == 0 || b.angle() == 0) puts("0.00");
else {
if (ya1 > yb1) xl = xa1, yl = ya1;
else xl = xb1, yl = yb1;
if (ya2 > yb2) xr = xa2, yr = ya2;
else xr = xb2, yr = yb2;
if (a.angle() < pi / 2 && b.angle() < pi / 2) {
if (a.angle() > b.angle() && xl >= xr && yl >= yr) { puts("0.00"); continue; }
if (a.angle() < b.angle() && xl <= xr && yl <= yr) { puts("0.00"); continue; }
Point cr = a.crosspoint(b);
int miny, minx;
Line seg;
if (yl < yr) miny = yl, minx = xl, seg = b;
else miny = yr, minx = xr, seg = a;
Line heng = Line(Point(minx, miny), Point(minx + 1, miny));
Point cr2 = heng.crosspoint(seg);
Point cr3;
if (minx == xl) cr3 = Point(xl, yl);
else cr3 = Point(xr, yr);
double temp = (cr2.x - cr.x) * (cr3.y - cr.y) - (cr3.x - cr.x) * (cr2.y - cr.y);
printf("%.2f\n", fabs(temp) / 2);
}
else if (a.angle() > pi / 2 && b.angle() > pi / 2) {
if (a.angle() > b.angle() && xl >= xr && yl <= yr) { puts("0.00"); continue; }
if (a.angle() < b.angle() && xl <= xr && yl >= yr) { puts("0.00"); continue; }
Point cr = a.crosspoint(b);
int miny, minx;
Line seg;
if (yl < yr) miny = yl, minx = xl, seg = b;
else miny = yr, minx = xr, seg = a;
Line heng = Line(Point(minx, miny), Point(minx + 1, miny));
Point cr2 = heng.crosspoint(seg);
Point cr3;
if (minx == xl) cr3 = Point(xl, yl);
else cr3 = Point(xr, yr);
double temp = (cr2.x - cr.x) * (cr3.y - cr.y) - (cr3.x - cr.x) * (cr2.y - cr.y);
printf("%.2f\n", fabs(temp) / 2);
}
else {
Point cr = a.crosspoint(b);
int miny, minx;
Line seg;
if (yl < yr) miny = yl, minx = xl, seg = b;
else miny = yr, minx = xr, seg = a;
Line heng = Line(Point(minx, miny), Point(minx + 1, miny));
Point cr2 = heng.crosspoint(seg);
Point cr3;
if (minx == xl) cr3 = Point(xl, yl);
else cr3 = Point(xr, yr);
double temp = (cr2.x - cr.x) * (cr3.y - cr.y) - (cr3.x - cr.x) * (cr2.y - cr.y);
printf("%.2f\n", fabs(temp) / 2);
}
}
}
}
return 0;
}
上一篇: 计算几何-----》两直线是否相交
下一篇: Revit二次开发_项目文件分离
推荐阅读
-
POJ2932Coneology(计算几何、平面扫描)
-
POJ - 2826 An Easy Problem?!(计算几何,好题)
-
计算几何 POJ 2653 Pick-up sticks
-
【计算几何+判断线段是否相交】HDU-1086 You can Solve a Geometry Problem too
-
2018.07.03 POJ 2653 Pick-up sticks(简单计算几何)
-
[计算几何]Grandpa's Estate[POJ1228]
-
[POJ3714] Raid 计算几何
-
POJ 1113 Wall(思维 计算几何 数学)
-
HDU5572 An Easy Physics Problem【计算几何】
-
【POJ1066】【UVA754】【计算几何】Treasure Hunt