hdu 4667 Building Fence 计算几何模板
生活随笔
收集整理的這篇文章主要介紹了
hdu 4667 Building Fence 计算几何模板
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
1 //大白p263
2 #include <cmath>
3 #include <cstdio>
4 #include <cstring>
5 #include <string>
6 #include <queue>
7 #include <functional>
8 #include <set>
9 #include <iostream>
10 #include <vector>
11 #include <algorithm>
12 using namespace std;
13 const double eps=1e-8;//精度
14 const int INF=0x3f3f3f3f;
15 const double PI=acos(-1.0);
16 inline int dcmp(const double& x){//判斷double等于0或。。。
17 if(fabs(x)<eps)return 0;else return x<0?-1:1;
18 }
19 struct Point{
20 double x,y;
21 Point(){}
22 Point(double x,double y):x(x),y(y){}
23 };
24 typedef Point Vector;
25 typedef vector<Point> Polygon;
26 inline Vector operator+(const Vector& a,const Vector& b){return Vector(a.x+b.x,a.y+b.y);}//向量+向量=向量
27 inline Vector operator-(const Point& a,const Point& b){return Vector(a.x-b.x,a.y-b.y);}//點-點=向量
28 inline Vector operator*(const Vector& a,const double& p){return Vector(a.x*p,a.y*p);}//向量*實數=向量
29 inline Vector operator/(const Vector& a,const double& p){return Vector(a.x/p,a.y/p);}//向量/實數=向量
30 inline bool operator<( const Point& A,const Point& B ){return dcmp(A.x-B.x)<0||(dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)<0);}
31 inline bool operator==(const Point&a,const Point&b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}
32 inline bool operator!=(const Point&a,const Point&b){return a==b?false:true;}
33 struct Segment{
34 Point a,b;
35 Segment(){}
36 Segment(Point _a,Point _b){a=_a,b=_b;}
37 inline bool friend operator<(const Segment& p,const Segment& q){return p.a<q.a||(p.a==q.a&&p.b<q.b);}
38 inline bool friend operator==(const Segment& p,const Segment& q){return (p.a==q.a&&p.b==q.b)||(p.a==q.b&&p.b==q.a);}
39 };
40 struct Circle{
41 Point c;
42 double r;
43 Circle(){}
44 Circle(Point _c, double _r):c(_c),r(_r) {}
45 Point point(double a)const{return Point(c.x+cos(a)*r,c.y+sin(a)*r);}
46 bool friend operator<(const Circle& a,const Circle& b){return a.r<b.r;}
47 };
48 struct Line{
49 Point p;
50 Vector v;
51 double ang;
52 Line() {}
53 Line(const Point &_p, const Vector &_v):p(_p),v(_v){ang = atan2(v.y, v.x);}
54 inline bool operator<(const Line &L)const{return ang < L.ang;}
55 };
56 inline double Dot(const Vector& a,const Vector& b){return a.x*b.x+a.y*b.y;}//|a|*|b|*cosθ 點積
57 inline double Length(const Vector& a){return sqrt(Dot(a,a));}//|a| 向量長度
58 inline double Angle(const Vector& a,const Vector& b){return acos(Dot(a,b)/Length(a)/Length(b));}//向量夾角θ
59 inline double Cross(const Vector& a,const Vector& b){return a.x*b.y-a.y*b.x;}//叉積 向量圍成的平行四邊形的面積
60 inline double Area2(const Point& a,const Point& b,Point c){return Cross(b-a,c-a);}//同上 參數為三個點
61 inline double DegreeToRadius(const double& deg){return deg/180*PI;}
62 inline double GetRerotateAngle(const Vector& a,const Vector& b){//向量a順時針旋轉theta度得到向量b的方向
63 double tempa=Angle(a,Vector(1,0));
64 if(a.y<0) tempa=2*PI-tempa;
65 double tempb=Angle(b,Vector(1,0));
66 if(b.y<0) tempb=2*PI-tempb;
67 if((tempa-tempb)>0) return tempa-tempb;
68 else return tempa-tempb+2*PI;
69 }
70 inline double torad(const double& deg){return deg/180*PI;}//角度化為弧度
71 inline Vector Rotate(const Vector& a,const double& rad){//向量逆時針旋轉rad弧度
72 return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
73 }
74 inline Vector Normal(const Vector& a){//計算單位法線
75 double L=Length(a);
76 return Vector(-a.y/L,a.x/L);
77 }
78 inline Point GetLineProjection(const Point& p,const Point& a,const Point& b){//點在直線上的投影
79 Vector v=b-a;
80 return a+v*(Dot(v,p-a)/Dot(v,v));
81 }
82 inline Point GetLineIntersection(Point p,Vector v,Point q,Vector w){//求直線交點 有唯一交點時可用
83 Vector u=p-q;
84 double t=Cross(w,u)/Cross(v,w);
85 return p+v*t;
86 }
87 int ConvexHull(Point* p,int n,Point* sol){//計算凸包
88 sort(p,p+n);
89 int m=0;
90 for(int i=0;i<n;i++){
91 while(m>1&&dcmp(Cross(sol[m-1]-sol[m-2],p[i]-sol[m-2]))<=0) m--;
92 sol[m++]=p[i];
93 }
94 int k=m;
95 for(int i=n-2;i>=0;i--){
96 while(m>k&&dcmp(Cross(sol[m-1]-sol[m-2],p[i]-sol[m-2]))<=0) m--;
97 sol[m++]=p[i];
98 }
99 if(n>0) m--;
100 return m;
101 }
102 double Heron(double a,double b,double c){//海倫公式
103 double p=(a+b+c)/2;
104 return sqrt(p*(p-a)*(p-b)*(p-c));
105 }
106 bool SegmentProperIntersection(const Point& a1,const Point& a2,const Point& b1,const Point& b2){//線段規范相交判定
107 double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);
108 double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
109 return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
110 }
111 double CutConvex(const int& n,Point* poly,const Point& a,const Point& b, vector<Point> result[3]){//有向直線a b 切割凸多邊形
112 vector<Point> points;
113 Point p;
114 Point p1=a,p2=b;
115 int cur,pre;
116 result[0].clear();
117 result[1].clear();
118 result[2].clear();
119 if(n==0) return 0;
120 double tempcross;
121 tempcross=Cross(p2-p1,poly[0]-p1);
122 if(dcmp(tempcross)==0) pre=cur=2;
123 else if(tempcross>0) pre=cur=0;
124 else pre=cur=1;
125 for(int i=0;i<n;i++){
126 tempcross=Cross(p2-p1,poly[(i+1)%n]-p1);
127 if(dcmp(tempcross)==0) cur=2;
128 else if(tempcross>0) cur=0;
129 else cur=1;
130 if(cur==pre){
131 result[cur].push_back(poly[(i+1)%n]);
132 }
133 else{
134 p1=poly[i];
135 p2=poly[(i+1)%n];
136 p=GetLineIntersection(p1,p2-p1,a,b-a);
137 points.push_back(p);
138 result[pre].push_back(p);
139 result[cur].push_back(p);
140 result[cur].push_back(poly[(i+1)%n]);
141 pre=cur;
142 }
143 }
144 sort(points.begin(),points.end());
145 if(points.size()<2){
146 return 0;
147 }
148 else{
149 return Length(points.front()-points.back());
150 }
151 }
152 double DistanceToSegment(Point p,Segment s){//點到線段的距離
153 if(s.a==s.b) return Length(p-s.a);
154 Vector v1=s.b-s.a,v2=p-s.a,v3=p-s.b;
155 if(dcmp(Dot(v1,v2))<0) return Length(v2);
156 else if(dcmp(Dot(v1,v3))>0) return Length(v3);
157 else return fabs(Cross(v1,v2))/Length(v1);
158 }
159 inline bool isPointOnSegment(const Point& p,const Segment& s){
160 return dcmp(Cross(s.a-p,s.b-p))==0&&dcmp(Dot(s.a-p,s.b-p))<0;
161 }
162 int isPointInPolygon(Point p, Point* poly,int n){//點與多邊形的位置關系
163 int wn=0;
164 for(int i=0;i<n;i++){
165 Point& p2=poly[(i+1)%n];
166 if(isPointOnSegment(p,Segment(poly[i],p2))) return -1;//點在邊界上
167 int k=dcmp(Cross(p2-poly[i],p-poly[i]));
168 int d1=dcmp(poly[i].y-p.y);
169 int d2=dcmp(p2.y-p.y);
170 if(k>0&&d1<=0&&d2>0)wn++;
171 if(k<0&&d2<=0&&d1>0)wn--;
172 }
173 if(wn) return 1;//點在內部
174 else return 0;//點在外部
175 }
176 double PolygonArea(Point* p,int n){//多邊形有向面積
177 double area=0;
178 for(int i=1;i<n-1;i++)
179 area+=Cross(p[i]-p[0],p[i+1]-p[0]);
180 return area/2;
181 }
182 int GetLineCircleIntersection(Line L,Circle C,Point& p1,Point& p2){//圓與直線交點 返回交點個數
183 double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y-C.c.y;
184 double e = a*a + c*c, f = 2*(a*b+c*d), g = b*b + d*d -C.r*C.r;
185 double delta = f*f - 4*e*g;
186 if(dcmp(delta) < 0) return 0;//相離
187 if(dcmp(delta) == 0) {//相切
188 p1=p1=L.p+L.v*(-f/(2*e));
189 return 1;
190 }//相交
191 p1=(L.p+L.v*(-f-sqrt(delta))/(2*e));
192 p2=(L.p+L.v*(-f+sqrt(delta))/(2*e));
193 return 2;
194 }
195 double rotating_calipers(Point *ch,int n)//旋轉卡殼
196 {
197 int q=1;
198 double ans=0;
199 ch[n]=ch[0];
200 for(int p=0;p<n;p++)
201 {
202 while(Cross(ch[q+1]-ch[p+1],ch[p]-ch[p+1])>Cross(ch[q]-ch[p+1],ch[p]-ch[p+1]))
203 q=(q+1)%n;
204 ans=max(ans,max(Length(ch[p]-ch[q]),Length(ch[p+1]-ch[q+1])));
205 }
206 return ans;
207 }
208 Polygon CutPolygon(Polygon poly,const Point& a,const Point& b){//用a->b切割多邊形 返回左側
209 Polygon newpoly;
210 int n=poly.size();
211 for(int i=0;i<n;i++){
212 Point c=poly[i];
213 Point d=poly[(i+1)%n];
214 if(dcmp(Cross(b-a,c-a))>=0) newpoly.push_back(c);
215 if(dcmp(Cross(b-a,c-d))!=0){
216 Point ip=GetLineIntersection(a,b-a,c,d-c);
217 if(isPointOnSegment(ip,Segment(c,d))) newpoly.push_back(ip);
218 }
219 }
220 return newpoly;
221 }
222 int GetCircleCircleIntersection(Circle c1,Circle c2,Point& p1,Point& p2){//求兩圓相交
223 double d=Length(c1.c-c2.c);
224 if(dcmp(d)==0){
225 if(dcmp(c1.r-c2.r)==0) return -1;//兩圓重合
226 return 0;
227 }
228 if(dcmp(c1.r+c2.r-d)<0) return 0;
229 if(dcmp(fabs(c1.r-c2.r)-d)>0) return 0;
230 double a=Angle(c2.c-c1.c,Vector(1,0));
231 double da=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
232 p1=c1.point(a-da);p2=c1.point(a+da);
233 if(p1==p2) return 1;
234 return 2;
235 }
236 inline bool isPointOnleft(Point p,Line L){return dcmp(Cross(L.v,p-L.p))>0;}//點在直線左邊 線上不算
237 int HalfplaneIntersection(Line *L,int n,Point* poly){//半平面交
238 sort(L,L+n);
239 int first,last;
240 Point* p=new Point[n];
241 Line* q=new Line[n];
242 q[first=last=0]=L[0];
243 for(int i=1;i<n;i++){
244 while(first<last&&!isPointOnleft(p[last-1],L[i])) last--;
245 while(first<last&&!isPointOnleft(p[first],L[i])) first++;
246 q[++last]=L[i];
247 if(dcmp(Cross(q[last].v,q[last-1].v))==0){
248 last--;
249 if(isPointOnleft(L[i].p,q[last])) q[last]=L[i];
250 }
251 if(first<last) p[last-1]=GetLineIntersection(q[last-1].p,q[last-1].v,q[last].p,q[last].v);
252 }
253 while(first<last&&!isPointOnleft(p[last-1],q[first])) last--;
254 if(last-first<=1) return 0;
255 p[last]=GetLineIntersection(q[last].p,q[last].v,q[first].p,q[first].v);
256 int m=0;
257 for(int i=first;i<=last;i++) poly[m++]=p[i];
258 return m;
259 }
260 //兩點式化為一般式A = b.y-a.y, B = a.x-b.x, C = -a.y*(B)-a.x*(A);
261 //--------------------------------------
262 //--------------------------------------
263 //--------------------------------------
264 //--------------------------------------
265 //--------------------------------------
266 Point point[444444],ppoint[444444];
267 int main()
268 {
269 int n,m;
270 while(~scanf("%d%d",&n,&m))
271 {
272 int tot = 0;
273 double x,y,r;
274 for(int i = 0;i<n;i++)
275 {
276 scanf("%lf%lf%lf",&x,&y,&r);
277 for(double j = 0;j<2*PI;j += 0.0032)
278 {
279 point[tot++] = Point(x+r*cos(j),y+r*sin(j));
280 }
281 }
282 for(int i = 0;i<m;i++)
283 for(int j = 0;j<3;j++)
284 {
285 scanf("%lf%lf",&x,&y);
286 point[tot++] = Point(x,y);
287 }
288 tot=ConvexHull(point,tot,ppoint);
289 double ans = 0;
290 Point pre = ppoint[0];
291 for(int i = 1;i<tot;i++)
292 {
293 ans += Length(ppoint[i]-pre);
294 pre = ppoint[i];
295 }
296 ans += Length(ppoint[0]-pre);
297 printf("%.5f\n",ans);
298 }
299 return 0;
300 } View Code
?
轉載于:https://www.cnblogs.com/jian1573/p/3258350.html
總結
以上是生活随笔為你收集整理的hdu 4667 Building Fence 计算几何模板的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ACM之常见的(C++版)问题解析
- 下一篇： 好记心不如烂笔头之jQuery学习,第一