当前位置: 代码迷 >> 综合 >> POJ 1279 Art Gallery .
  详细解决方案

POJ 1279 Art Gallery .

热度:60   发布时间:2023-09-23 08:38:31.0

题目地址:http://poj.org/problem?id=1279

求完面积要取绝对值,输出答案要用%f而不是%lf

模板题,直接套模板就好了

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define Vector Point
const double EPS=1e-6;
int Sign(double x){ if(fabs(x)<EPS) return 0;return x<0?-1:1;
}
struct Point{double x,y;Point(double x,double y):x(x),y(y){}Vector operator - (const Point& p){return Vector(x-p.x,y-p.y);}double operator * (const Vector& v){return x*v.x+y*v.y;}
}; 
double cross(const Point& a,const Point& b){return a.x*b.y-a.y*b.x;
}
Vector operator * (double k,Vector p){  //c=f*|a|;return Vector(k*p.x,k*p.y);
}
Vector operator + (Point a,Vector b){return Vector(a.x+b.x,a.y+b.y);
}
bool operator == (Point a,Point b){return Sign(a.x-b.x)==0&&Sign(a.y-b.y)==0;
}
struct Seg{Point a,b;Seg(const Point& a,const Point& b):a(a),b(b){}
}; typedef vector<Point> Polygon;//两条线段相交的各种情况
//结果保存在pair<int,Point> 中 
//返回值 result.first:
//0 规范相交,
//1 端点重合,但不平行,不共线
//2 一个端点在另一个内部 s1端点在 s2内部 (不平行,不共线)
//3 一个端点在另一个内部 s2端点在 s1内部 (不平行,不共线)
//4 无交点,不平行,不共线,两直线交点是result.second
//5 平行
//6 共线且有公共点
//7 共线且无公共点
//8 s1,s2无交点,但是s2所在直线和s1有交点,即交点在s1上
//9 s1,s2无交点,但是s1所在直线和s2有交点,即交点在s2上
bool FLessEq(double a,double b){ //b不小于a return Sign(b-a)>=0;
} 
double length(Vector p){  //求|p| return sqrt(p*p);
}
double dist(Point p,Seg s){return fabs(cross(p-s.a,s.b-s.a))/length(s.b-s.a); //面积除以高
}
bool PointInSeg(Point p,Seg L){  //p点在线段l内 double tmp = cross(L.a-p,L.a-L.b);if(Sign(tmp)) return false;if(FLessEq(min(L.a.x,L.b.x),p.x) &&FLessEq(p.x,max(L.a.x,L.b.x)) &&FLessEq(min(L.a.y,L.b.y),p.y) &&FLessEq(p.y,max(L.a.y,L.b.y)) )return true;return false;
} 
pair<int,Point> CrossPoint(Seg s1,Seg s2){Point p1=s1.a;Point p2=s1.b;Point p3=s2.a;Point p4=s2.b;double a1 = cross(p3-p1,p4-p1); double a2 = cross(p4-p2,p3-p2);if(Sign(cross(p2-p1,p3-p1))*Sign(cross(p2-p1,p4-p1)) < 0&& Sign(cross(p4-p3,p1-p3))*Sign(cross(p4-p3,p2-p3)) < 0)return make_pair(0,p1+(a1/(a1+a2))*(p2-p1)); //规范相交if(Sign(cross(p2-p1,p3-p4))){  //不平行不共线if(p1==p3||p1==p4) return make_pair(1,p1);if(p2==p3||p2==p4) return make_pair(1,p2);if(PointInSeg(p1,s2)) return make_pair(2,p1);if(PointInSeg(p2,s2)) return make_pair(2,p2);if(PointInSeg(p3,s1)) return make_pair(3,p3);if(PointInSeg(p4,s1)) return make_pair(3,p4);Point crossPoint = p1+(a1/(a1+a2))*(p2-p1); //交点 if(PointInSeg(crossPoint,s1)) return make_pair(8,crossPoint);if(PointInSeg(crossPoint,s2)) return make_pair(9,crossPoint);//直线和线段也无交点 不平行 不共线 两直线交点是second return make_pair(4,crossPoint);  	} if(Sign(dist(p1,s2))) return make_pair(5,Point(0,0));  //平行//共线  且有公共点 if(PointInSeg(p1,s2))   return make_pair(6,p1);if(PointInSeg(p2,s2))   return make_pair(6,p2);if(PointInSeg(p3,s1))   return make_pair(6,p3);if(PointInSeg(p4,s1))   return make_pair(6,p4);return make_pair(7,Point(0,0));//共线 且无公共点
}int CutPloygon(Point a,Point b,const Polygon& src,Polygon& result)
{//直线a->b,切割src,返回其左边的多边形,放到result中 int n=src.size();  //src中的点并不需要排序 result.clear();for(int i=0;i<n;i++){Point c=src[i];    //取出相邻的两个点 Point d=src[(i+1)%n];if(Sign(cross(b-a,c-a))>=0) //c点在a->b左侧或上面 result.push_back(c);pair<int,Point> r=CrossPoint(Seg(c,d),Seg(a,b));if(r.first==0||r.first==8||r.first==3) result.push_back(r.second);	//相交的话把交点放入}} Polygon s,r,points;int main(){int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);points.clear();for(int i=0;i<n;i++){int x,y;scanf("%d%d",&x,&y);points.push_back(Point(x,y));}s=points;for(int i=n-1;i>=0;i--){Point a=points[(i+1)%n],b=points[i];CutPloygon(a,b,s,r);s=r;}double area=0;for(int i=0;i<s.size();i++)area+=cross(s[(i+1)%s.size()],s[i]);area/=2;printf("%.2f\n",fabs(area));}return 0;}


  相关解决方案