赣州制作网站百度,太原电商网站设计,品牌建设成果,网站建设图片素材库题意#xff1a;给出一些点#xff0c;求最小的覆盖这些点的矩形的面积。 题解#xff1a; 枚举下边界#xff08;是一条边#xff09;#xff0c;然后暴力卡壳左右边界#xff08;点#xff09;#xff0c;再暴力上边界#xff08;点#xff09;#xff0c;更新答…题意给出一些点求最小的覆盖这些点的矩形的面积。 题解 枚举下边界是一条边然后暴力卡壳左右边界点再暴力上边界点更新答案。 View Code 1 #include iostream2 #include cstdio3 #include cstdlib4 #include cstring5 #include algorithm6 #include cmath7 8 #define N 22229 #define EPS 1e-710 #define INF 1e2011 12 using namespace std;13 14 struct PO15 {16 double x,y;17 }p[N],stk[N],o;18 19 int n,top;20 int s[10];21 double ans;22 23 inline int dc(double x)24 {25 if(xEPS) return 1;26 else if(x-EPS) return -1;27 return 0;28 }29 30 inline bool cmp(const PO a,const PO b)31 {32 if(dc(a.x-b.x)0) return a.yb.y;33 return a.xb.x;34 }35 36 inline PO operator (PO a,PO b)37 {38 PO c;39 c.xa.xb.x;40 c.ya.yb.y;41 return c;42 }43 44 inline PO operator -(PO a,PO b)45 {46 PO c;47 c.xa.x-b.x;48 c.ya.y-b.y;49 return c;50 }51 52 inline double cross(PO a,PO b,PO c)53 {54 return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);55 }56 57 inline double getangle(PO a,PO b,POc,PO d)58 {59 PO tc(a-d);60 return cross(b,a,t);61 }62 63 inline PO getfline(PO a,PO b,PO c)//得到垂线 64 {65 PO dc-b,e;66 e.xa.x-d.y;67 e.ya.yd.x;68 return e;69 }70 71 inline double getdis(PO a,PO b)72 {73 return sqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y));74 }75 76 inline double getdis_ps(PO a,PO b,PO c)77 {78 return fabs(cross(a,b,c))/getdis(b,c);79 }80 81 inline void getside()82 {83 for(int i0;i4;i) s[i]0;84 for(int i1;itop;i)85 {86 if(dc(stk[i].y-stk[s[0]].y)0) s[0]i;87 if(dc(stk[i].x-stk[s[1]].x)0) s[1]i;88 if(dc(stk[i].y-stk[s[2]].y)0) s[2]i;89 if(dc(stk[i].x-stk[s[3]].x)0) s[3]i;90 }91 // 0 ymin, 1 xmin, 2 ymax ,3 xmax;92 }93 94 inline void rotating_calipers()95 {96 getside();97 int tmps[0];98 ansINF;99 do
100 {//枚举下边界直线
101 PO tgetfline(stk[s[0]],stk[s[0]],stk[(s[0]1)%top]);
102 while(dc(getangle(t,stk[s[0]],stk[s[1]],stk[(s[1]1)%top]))0) s[1](s[1]1)%top;//卡右边界
103 while(dc(getangle(stk[s[0]],t,stk[s[3]],stk[(s[3]1)%top]))0) s[3](s[3]1)%top;//卡做边界
104 while(dc(getdis_ps(stk[(s[2]1)%top],stk[s[0]],stk[(s[0]1)%top])-
105 getdis_ps(stk[s[2]],stk[s[0]],stk[(s[0]1)%top]))0) s[2](s[2]1)%top;//卡上边界
106 double agetdis_ps(stk[s[2]],stk[s[0]],stk[(s[0]1)%top]);
107 tgetfline(stk[s[3]],stk[s[0]],stk[(s[0]1)%top]);
108 double bgetdis_ps(stk[s[1]],stk[s[3]],t);
109 ansmin(ans,a*b);
110 s[0](s[0]1)%top;
111 }while(s[0]!tmp);
112 }
113
114 inline void graham()
115 {
116 sort(p1,p1n,cmp);
117 top-1;
118 stk[top]p[1]; stk[top]p[2];
119 for(int i3;in;i)
120 {
121 while(top1dc(cross(stk[top-1],stk[top],p[i]))0) top--;
122 stk[top]p[i];
123 }
124 int tmptop;
125 for(int in-1;i1;i--)
126 {
127 while(toptmp1dc(cross(stk[top-1],stk[top],p[i]))0) top--;
128 stk[top]p[i];
129 }
130 }
131
132 inline void read()
133 {
134 for(int i1;in;i) scanf(%lf%lf,p[i].x,p[i].y);
135 }
136
137 inline void go()
138 {
139 if(n2) ans0.0;
140 else graham(),rotating_calipers();
141 printf(%.4lf\n,ans);
142 }
143
144 int main()
145 {
146 while(~scanf(%d,n)n) read(),go();
147 return 0;
148 } 这题傻X了凸包写错了。。查了好久都改得和题解一样了。。。~~~~(_)~~~~ 一下自己yy的。 View Code 1 #include iostream2 #include cstring3 #include cstdio4 #include cstdlib5 #include algorithm6 #include cmath7 8 #define N 20209 #define EPS 1e-710 11 using namespace std;12 13 struct PO14 {15 double x,y;16 inline void prt() {printf(%lf %lf\n,x,y);}17 }p[N],stk[N],res[N],o;18 19 int n,tot;20 21 inline void read()22 {23 for(int i1;in;i) scanf(%lf%lf,p[i].x,p[i].y);24 }25 26 inline int dc(double x)27 {28 if(xEPS) return 1;29 else if(x-EPS) return -1;30 return 0;31 }32 33 inline bool cmp(const PO a,const PO b)34 {35 if(dc(a.x-b.x)0) return a.yb.y;36 return a.xb.x;37 }38 39 inline PO operator (PO a,PO b)40 {41 a.xb.x; a.yb.y;42 return a;43 }44 45 inline PO operator -(PO a,PO b)46 {47 a.x-b.x; a.y-b.y;48 return a;49 }50 51 inline double cross(PO a,PO b,PO c)52 {53 return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);54 }55 56 inline double dot(PO a,PO b,PO c)57 {58 return (b.x-a.x)*(c.x-a.x)(b.y-a.y)*(c.y-a.y);59 }60 61 inline double getdis(PO a,PO b)62 {63 return sqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y));64 }65 66 inline void graham()67 {68 sort(p1,p1n,cmp);69 tot-1; int top0;70 for(int i1;in;i)71 {72 while(top2dc(cross(stk[top-1],stk[top],p[i]))0) top--;73 stk[top]p[i];74 }75 for(int i1;itop;i) res[tot]stk[i];76 top0;77 for(int in;i1;i--)78 {79 while(top2dc(cross(stk[top-1],stk[top],p[i]))0) top--;80 stk[top]p[i];81 }82 for(int i2;itop;i) res[tot]stk[i];83 }84 85 inline int getangle_dot(PO a,PO b,PO c,PO d)86 {87 PO ed-(c-a);88 return dc(dot(a,b,e));89 }90 91 inline double getangle_cross(PO a,PO b,PO c,PO d)92 {93 PO ed-(c-a);94 return dc(cross(a,b,e));95 }96 97 inline double getlen(PO a)98 {99 return sqrt(a.x*a.xa.y*a.y);
100 }
101
102 inline double getty(PO a,PO b)
103 {
104 return dot(o,a,b)/getlen(b);
105 }
106
107 inline void rotating_calipers()
108 {
109 double ans1e20;
110 PO sa,sb;
111 for(int i0;itot;i)
112 {
113 int rt(i1)%tot;
114 while(getangle_dot(res[i],res[(i1)%tot],res[rt],res[(rt1)%tot])0) rt(rt1)%tot;
115 int lti;
116 while(getangle_dot(res[i],res[(i1)%tot],res[(lt-1tot)%tot],res[lt])0) lt(lt-1tot)%tot;
117 int usp(i1)%tot;
118 while(getangle_cross(res[i],res[i1],res[usp],res[(usp1)%tot])0) usp(usp1)%tot;
119 double hfabs(cross(res[i],res[i1],res[usp]))/getdis(res[i],res[i1]);
120 sares[rt]-res[lt]; sbres[i1]-res[i];
121 ansmin(ans,fabs(h*getty(sa,sb)));
122 }
123 printf(%.4lf\n,ans);
124 }
125
126 inline void go()
127 {
128 graham();
129 if(tot2) printf(0.0000\n);
130 else if(tot3) printf(%.4lf\n,fabs(cross(res[0],res[1],res[2])));
131 else rotating_calipers();
132 }
133
134 int main()
135 {
136 while(scanf(%d,n),n)read(),go();
137 return 0;
138 } 转载于:https://www.cnblogs.com/proverbs/archive/2013/02/25/2932721.html
