本文主要是介绍poj 2826 计算几何,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
(代码后面给出了一些样例,都过了的话应该是没有)
乍一看就是个水题,实际上奥妙重重!!!
主要是由一种上面线段覆盖下面线段的情况,开始没注意到。
这种情况显然输出0。
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<ctime>
using namespace std;
void fre(){freopen("t.txt","r",stdin);}
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
#define ls o<<1
#define rs o<<1|1
#define MS(x,y) memset(x,y,sizeof(x))
#define debug(x) printf("%d",x);
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
const int INF = 1<<30;
const int MAXN = 105;
const double eps = 1e-8;
const double pi = acos(-1.0);int sgn(double x)
{if(fabs(x) < eps) return 0;if(x < 0) return -1;else return 1;
}
struct Point
{double x,y;Point(){}Point(double _x,double _y){x = _x; y = _y;}void input(){scanf("%lf%lf",&x,&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;}
};
struct Line
{Point s,e;Line(){}Line(Point _s,Point _e){s = _s; e = _e;}double getk(){return (s.y-e.y)/(s.x-e.x);}bool parallel(Line v){return sgn((e-s)^(v.e-v.s)) == 0;}void input(){e.input(); s.input();if(s.y < e.y) swap(s,e);}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);}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));}
}l1,l2;
int main()
{//fre();int T;double ans;scanf("%d",&T);while(T--){l1.input(); l2.input();if(l1.s.y > l2.s.y) swap(l1,l2);int flag = l1.segcrossseg(l2);if(flag == 0 || l1.parallel(l2) || sgn(l1.e.y - l1.s.y) == 0 || sgn(l2.e.y - l2.s.y) == 0)//与x平行,或无交点,或重合{printf("0.00\n"); continue;}Point jiao = l1.crosspoint(l2);Point u = l1.s;Point v = u; v.x += 1;Line l3 = Line(u,v);v = l2.crosspoint(l3);if(sgn(l1.s.x - l1.e.x) != 0 && sgn(l2.s.x - l2.e.x) != 0)//完全覆盖{double k1 = l1.getk(),k2 = l2.getk();if(k1*k2 > 0){if(k1 > k2 && l1.s.x > l2.s.x - eps) goto stop;if(k1 < k2 && l2.s.x > l1.s.x - eps) goto stop;}}ans = (fabs(u.x-v.x)*fabs(u.y - jiao.y))/2;printf("%.2f\n",ans); continue;stop:printf("0.00\n");}
}
/*
10
6259 2664 8292 9080
1244 2972 9097 96800 1 1 0
1 0 2 10 1 2 1
1 0 1 20 0 10 10
0 0 9 80 0 10 10
0 0 8 90.9 3.1 4 0
0 3 2 20 0 0 2
0 0 -3 21 1 1 4
0 0 2 31 2 1 4
0 0 2 31 4 3 1
1 3 4 1
输出:
6162.65
1.00
0.00
0.00
4.50
0.50
3.00
0.75
0.00
0.00
*/
这篇关于poj 2826 计算几何的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!