?

POJ 1981：Circle and Points

/*題目大意：給出平面上一些點，問一個半徑為1的圓最多可以覆蓋幾個點題解：我們對于每個點畫半徑為1的圓，那么在兩圓交弧上的點所畫的圓，一定可以覆蓋這兩個點我們對于每個點計算出其和其它點的交弧，對這些交弧計算起末位置對于圓心的極角，對這些我們進行掃描線操作，統計最大交集數量就是答案。 */ #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> using namespace std; double EPS=1e-10; double add(double a,double b){if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;return a+b; } const int MAX_N=310; struct P{double x,y;P(){}P(double x,double y):x(x),y(y){}P operator + (P p){return P(add(x,p.x),add(y,p.y));}P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}P operator * (double d){return P(x*d,y*d);}double dot(P p){return add(x*p.x,y*p.y);} //點積double det(P p){return add(x*p.y,-y*p.x);} //叉積 }ps[MAX_N]; double dist(P p,P q){return sqrt((p-q).dot(p-q));} struct PolarAngle{double angle;bool flag; }as[MAX_N]; bool cmp_a(PolarAngle a,PolarAngle b){return a.angle<b.angle; } int solve(int n,double r){int ans=1;for(int i=0;i<n;i++){int m=0; double d;for(int j=0;j<n;j++){if(i!=j&&(d=dist(ps[i],ps[j]))<=2*r){double phi=acos(d/2);double theta=atan2(ps[j].y-ps[i].y,ps[j].x-ps[i].x);as[m].angle=theta-phi,as[m++].flag=1;as[m].angle=theta+phi,as[m++].flag=0;}}sort(as,as+m,cmp_a);for(int sum=1,j=0;j<m;j++){if(as[j].flag)sum++;else sum--;ans=max(ans,sum);}}return ans; } int N; int main(){while(scanf("%d",&N),N){for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);printf("%d\n",solve(N,1.0));}return 0; }

POJ 1418：Viva Confetti

/*給出一些圓的位置和半徑以及疊放次序，問能看到的有幾個圓 */ #include <cstring> #include <algorithm> #include <cmath> #include <complex> #include <vector> #include <cstdio> using namespace std; typedef complex<double> P; #define M_PI 3.14159265358979323846 const double EPS=4E-13; double Tran(double r){while(r<0.0)r+=2*M_PI;while(r>=2*M_PI)r-=2*M_PI;return r; } int hit_test(P p,vector<P>&points,vector<double> &rs){for(int i=rs.size()-1;i>=0;i--){if(abs(points[i]-p)<rs[i])return i;}return -1; } int n; int main(){while(scanf("%d",&n),n){vector<P> points;vector<double> rs;for(int i=0;i<n;i++){double x,y,r;scanf("%lf%lf%lf",&x,&y,&r);points.push_back(P(x,y));rs.push_back(r);}vector<bool> visible(n,false);for(int i=0;i<n;i++){vector<double> rads;rads.push_back(0.0);rads.push_back(2.0*M_PI);for(int j=0;j<n;j++){double a=rs[i],b=abs(points[j]-points[i]),c=rs[j];if(a+b<c||a+c<b||b+c<a)continue;double d=arg(points[j]-points[i]);double e=acos((a*a+b*b-c*c)/(2*a*b));rads.push_back(Tran(d+e));rads.push_back(Tran(d-e));}sort(rads.begin(),rads.end());for(int j=0;j<rads.size()-1;j++){double rad=(rads[j+1]+rads[j])/2.0;for(int k=-1;k<=1;k+=2){int t=hit_test(P(points[i].real()+(rs[i]+EPS*k)*cos(rad),points[i].imag()+(rs[i]+EPS*k)*sin(rad)),points,rs);if(t!=-1)visible[t]=true;}}}printf("%d\n",count(visible.begin(),visible.end(),true));}return 0; }

AOJ 2201：Immortal Jewels

/*題目大意：給出一些圓，求一條直線最多與幾個圓相切題解：我們枚舉任意兩個圓的切線，然后計算與這條切線相切的圓的數目即可。 */ #include <iostream> #include <vector> #include <complex> #include <cmath> #include <algorithm> using namespace std; typedef complex<double> P; const double PI=acos(-1); const double EPS=1e-12; int cmp(double a,double b){const double diff=a-b;if(fabs(diff)<EPS)return 0;else if(diff<0)return -1;else return 1; } inline double dot(const P &a, const P &b){return a.real()*b.real()+a.imag()*b.imag(); } inline double cross(const P &a, const P &b){return a.real()*b.imag()-b.real()*a.imag(); } struct line{P a,b;line(){}line(const P &p,const P &q):a(p),b(q){}// 是否平行inline bool parallel(const line &ln) const{return abs(cross(ln.b-ln.a,b-a))<EPS; //平行叉乘得到向量的模是0，也就是sin(theta)=0<->theta=0}// 是否相交inline bool intersects(const line &ln) const{return !parallel(ln);}// 求交點inline P intersection(const line &ln) const{const P x=b-a;const P y=ln.b-ln.a;return a+x*(cross(y,ln.a-a))/cross(y,x);}// 點到直線的距離inline double distance(const P &p) const{return abs(cross(p-a,b-a))/abs(b-a);}// 求垂足坐標inline P perpendicular(const P &p) const{const double t=dot(p-a,a-b)/dot(b-a,b-a);return a+t*(a-b);} }; struct circle{P o;double r;circle(){}circle(const P &p,double x):o(p),r(x){}// 通過點 p 的兩條切線pair<P,P> tangent(const P &p)const{const double L=abs(o-p);const double M=sqrt(L*L-r*r);const double theta=asin(r/L);const P v=(o-p)/L;return make_pair(p+M*(v*polar(1.0,theta)),p+M*(v*polar(1.0,-theta)));}// 兩個半徑相等圓的兩條平行外切線pair<line,line> outer_tangent_parallel(const circle &c) const{const P d=o-c.o;const P v=d*P(0,1)*r/abs(d);return make_pair(line(o+v,c.o+v),line(o-v,c.o-v));}// 兩個圓外切線pair<line,line> outer_tangent(const circle &c) const{if(cmp(r,c.r)==0)return outer_tangent_parallel(c);if(r>c.r)return c.outer_tangent(*this);const P d=o-c.o;const double fact=c.r/r-1;const P base=c.o+d+d/fact;const pair<P, P> t=tangent(base);return make_pair(line(base,t.first),line(base,t.second));}// 內切線pair<line,line> inner_tangent(const circle &c) const{if(r>c.r)return c.inner_tangent(*this);const P d=c.o-o;const double fact=c.r/r+1;const P base=o+d/fact;const pair<P,P> t=tangent(base);return make_pair(line(base,t.first),line(base,t.second));}// 是否相交inline bool intersects(const circle &c) const{return !contains(c)&&!c.contains(*this)&&cmp(abs(o-c.o),r+c.r)<=0;}// 是否相離inline bool independent(const circle &c) const{return cmp(abs(o-c.o),r+c.r)>0;}// 兩個圓的交點pair<P,P> intersection(const circle &c) const{const double d=abs(o-c.o);const double cos_=(d*d+r*r-c.r*c.r)/(2*d);const double sin_=sqrt(r*r-cos_*cos_);const P e=(c.o-o)/d;return make_pair(o+e*P(cos_,sin_),o+e* P(cos_,-sin_));}// 是否包含圓cinline bool contains(const circle &c) const{return cmp(abs(o-c.o)+c.r,r)<0;}// 是否相交inline bool intersects(const line &ln) const{return cmp(abs(ln.distance(o)),r)<=0;}// 圓心到直線的距離inline double distance(const line &ln) const{return abs(ln.distance(o));}// 圓與直線的交點pair<P,P> intersection(const line &ln) const{const P h=ln.perpendicular(o);const double d=abs(h-o);P ab=ln.b-ln.a;ab/=abs(ab);const double l=sqrt(r*r-d*d);return make_pair(h+l*ab,h-l*ab);} }; void enum_event(const circle &c1,const circle &c2,vector<line> &lines){if(c1.independent(c2)){pair<line,line> outer=c1.outer_tangent(c2);lines.push_back(outer.first);lines.push_back(outer.second);pair<line,line> inner = c1.inner_tangent(c2);lines.push_back(inner.first);lines.push_back(inner.second);}else if (c1.intersects(c2)){pair<line,line> outer=c1.outer_tangent(c2);lines.push_back(outer.first);lines.push_back(outer.second);pair<P,P> inter=c1.intersection(c2);lines.push_back(line(inter.first,inter.second)); // 此時內切線不存在，使用交點形成的線代替} } bool solve(){int N;scanf("%d",&N);if(!N)return false;vector<pair<circle,circle> > jewels;vector<line> lines;for(int i=0;i<N;i++){double x,y,r,m;scanf("%lf%lf%lf%lf",&x,&y,&r,&m);const P center(x,y);pair<circle,circle> jewel=make_pair(circle(center,r),circle(center,r+m));for(const auto &other:jewels){enum_event(jewel.first,other.first,lines);enum_event(jewel.first,other.second,lines);enum_event(jewel.second,other.first,lines);enum_event(jewel.second,other.second,lines);}jewels.push_back(jewel);}int ans=1;for(auto &l:lines){int cnt=count_if(jewels.begin(),jewels.end(),[&](const pair<circle,circle> &j){ // [&] 按引用捕獲在lambda表達式所在函數的函數體中提及的全部自動儲存持續性變量return cmp(j.first.r, j.first.distance(l))<=0&&cmp(j.second.r,j.second.distance(l))>=0; // 在磁力圓范圍內且不在本體范圍內});ans=max(ans, cnt);}printf("%d\n",ans);return 1; } int main(){while(solve());return 0; }

POJ 3168：Barn Expansion

/*題目大意：給出一些矩形，沒有相交和包含的情況，只有相切的情況問有多少個矩形沒有相切或者邊角重疊題解：我們將所有的與x軸平行的線段和與y周平行的線段分開處理，判斷是否出現重合對重合的兩個矩形進行標識，最后沒有被標識過的矩形數目就是答案。 */ #include <cstdio> #include <vector> #include <algorithm> #include <cstring> using namespace std; const int N=30010; struct data{int id,d,x,y;data(){}; data(int _d,int _x,int _y,int _id):d(_d),x(_x),y(_y),id(_id){} }; vector<data> sx,sy; bool vis[N]; bool cmp(data a,data b){if(a.d!=b.d)return a.d<b.d;if(a.x!=b.x)return a.x<b.x;return a.y<b.y; } int n,a,b,c,d; void solve(){sx.clear();sy.clear();memset(vis,0,sizeof(vis));for(int i=0;i<n;i++){scanf("%d%d%d%d",&a,&b,&c,&d);sy.push_back(data(b,a,c,i));sy.push_back(data(d,a,c,i)); sx.push_back(data(a,b,d,i)); sx.push_back(data(c,b,d,i));}sort(sx.begin(),sx.end(),cmp);sort(sy.begin(),sy.end(),cmp);int t=sy[0].y;for(int i=1;i<sy.size();i++){if(sy[i-1].d==sy[i].d){if(t>=sy[i].x){vis[sy[i].id]=vis[sy[i-1].id]=1;}}else t=sy[i].y;t=max(sy[i].y,t);}t=sx[0].y;for(int i=1;i<sx.size();i++){if(sx[i-1].d==sx[i].d){if(t>=sx[i].x){vis[sx[i].id]=vis[sx[i-1].id]=1;}}else t=sx[i].y;t=max(sx[i].y,t);}int ans=0;for(int i=0;i<n;i++)if(!vis[i])ans++;printf("%d\n",ans); } int main(){while(~scanf("%d",&n))solve();return 0; }

POJ 3293：Rectilinear polygon

/*題目大意：給出一些點，每個點只能向外引出一條平行X軸，和Y軸的邊，問能否構成一個閉多邊形，如果能，返回多邊形的總邊長，否則返回-1題解：我們發現對于每一行或者每一列都必須有偶數個點，且兩兩之間相鄰才能滿足條件所以我們將其連線之后判斷是否可以構成一個封閉圖形，同時還需要判斷這些線是否會相交，如果相交即不成立 */ #include <cstdio> #include <algorithm> using namespace std; const int N=100010; struct Point{int x,y,id;}p[N]; struct Line{int d,x,y;Line(){}Line(int _d,int _x,int _y):d(_d),x(_x),y(_y){} }l[N]; int cmp_x(Point a,Point b){if(a.x==b.x)return a.y<b.y;return a.x<b.x; } int cmp_y(Point a,Point b){if(a.y==b.y)return a.x<b.x;return a.y<b.y; } int con[N][2],n,ln,T; int Check(Point a,Point b){int y=a.y,x1=a.x,x2=b.x;for(int i=0;i<ln;i++){if(x1<l[i].d&&x2>l[i].d&&l[i].x<y&&l[i].y>y)return 1;}return 0; } int main(){scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&p[i].x,&p[i].y);p[i].id=i;}int s=0,cnt=1,flag=0;ln=0;sort(p,p+n,cmp_x);for(int i=1;i<n&&!flag;i++){if(p[i].x!=p[i-1].x){if(cnt&1)flag=1;cnt=1;}else{cnt++;if((cnt&1)==0){s+=p[i].y-p[i-1].y;con[p[i].id][0]=p[i-1].id;con[p[i-1].id][0]=p[i].id;l[ln++]=Line(p[i].x,p[i-1].y,p[i].y);}}}sort(p,p+n,cmp_y);cnt=1;for(int i=1;i<n&&!flag;i++){if(p[i].y!=p[i-1].y){if(cnt&1)flag=1;cnt=1;}else{cnt++;if((cnt&1)==0){s+=p[i].x-p[i-1].x;con[p[i].id][1]=p[i-1].id;con[p[i-1].id][1]=p[i].id;if(Check(p[i-1],p[i]))flag=1;}}}int t=1,x=0,c=0;for(;;){x=con[x][t];t^=1; c++;if(x==0||flag)break;}if(c!=n)flag=1;if(flag)puts("-1");else printf("%d\n",s);}return 0; }

POJ 2482：Stars in Your Window

/*題目大意：給出一些點的二維坐標和權值，求用一個長H，寬W的矩形能框住的最大權值之和，在矩形邊緣的點不計算在內題解：我們計算能掃到這個點的區間范圍，將其拆分為兩條平行于y軸的左閉右開的直線，為方便邊界處理，我們將坐標擴大兩倍，之后我們按照x軸對這些線段進行掃描統計出現的最大值即可。 */ #include <cstdio> #include <algorithm> #include <utility> using namespace std; typedef long long LL; const int N=10010; LL xs[N],ys[N],X[N<<1],Y[N<<1]; int cs[N],tag[N<<3],T[N<<3]; pair<pair<int,int>,pair<int,int> >event[N<<1]; void update(int L,int R,int v,int x,int l,int r){if(L<=l&&r<=R){T[x]+=v;tag[x]+=v;return;}int mid=(l+r)>>1;if(L<=mid)update(L,R,v,x<<1,l,mid);if(mid<R)update(L,R,v,x<<1|1,mid+1,r);T[x]=max(T[x<<1],T[x<<1|1])+tag[x]; } int n,W,H; void solve(){for(int i=0;i<n;i++){scanf("%lld%lld%d",xs+i,ys+i,cs+i);xs[i]<<=1; ys[i]<<=1;}for(int i=0;i<n;i++){X[i<<1]=xs[i]-W; X[i<<1|1]=xs[i]+W;Y[i<<1]=ys[i]-H; Y[i<<1|1]=ys[i]-1+H;}sort(X,X+n*2);sort(Y,Y+n*2);for(int i=0;i<n;i++){event[i<<1]=make_pair(make_pair(lower_bound(X,X+n*2,xs[i]-W)-X,cs[i]),make_pair(lower_bound(Y,Y+n*2,ys[i]-H)-Y,lower_bound(Y,Y+n*2,ys[i]+H-1)-Y));event[i<<1|1]=make_pair(make_pair(lower_bound(X,X+n*2,xs[i]+W)-X,-cs[i]),make_pair(lower_bound(Y,Y+n*2,ys[i]-H)-Y,lower_bound(Y,Y+n*2,ys[i]+H-1)-Y));}sort(event,event+n*2);int ans=0;for(int i=0;i<n*2;i++){ update(event[i].second.first,event[i].second.second,event[i].first.second,1,0,n*2);ans=max(ans,T[1]);}printf("%d\n",ans); } int main(){while(~scanf("%d%d%d",&n,&W,&H))solve();return 0; }

POJ 1113：Wall

/*題目大意：給出一個城堡，要求求出距城堡距離大于L的地方建圍墻將城堡圍起來求所要圍墻的長度題解：畫圖易得答案為凸包的周長加一個圓的周長。 */ #include <cstdio> #include <algorithm> #include <cmath> #include <vector> using namespace std; double EPS=1e-10; const double PI=acos(-1.0); double add(double a,double b){if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;return a+b; } struct P{double x,y;P(){}P(double x,double y):x(x),y(y){}P operator + (P p){return P(add(x,p.x),add(y,p.y));}P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}P operator * (double d){return P(x*d,y*d);}double dot(P p){return add(x*p.x,y*p.y);} //點積double det(P p){return add(x*p.y,-y*p.x);} //叉積 }; bool cmp_x(const P& p,const P& q){if(p.x!=q.x)return p.x<q.x;return p.y<q.y; } vector<P> convex_hull(P* ps,int n){sort(ps,ps+n,cmp_x);int k=0;vector<P> qs(n*2);for(int i=0;i<n;i++){while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;qs[k++]=ps[i];}for(int i=n-2,t=k;i>=0;i--){while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;qs[k++]=ps[i];}qs.resize(k-1);return qs; } double dist(P p,P q){return sqrt((p-q).dot(p-q));} const int MAX_N=1000; int N,L; P ps[MAX_N]; vector<P> con; void solve(){for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);con=convex_hull(ps,N);double res=0;for(int i=0;i<con.size()-1;i++)res+=dist(con[i],con[i+1]);res+=dist(con[0],con[con.size()-1]);res+=2*PI*L;printf("%d\n",(int)(res+0.5)); } int main(){while(~scanf("%d%d",&N,&L))solve();return 0; }

POJ 1912：A highway and the seven dwarfs

/*題目大意：給出一些點，表示一些屋子，這些屋子共同組成了村莊，現在要建一些高速公路問是否經過了村莊。題解：這些屋子的關鍵點一定在凸包上，所以我們只要求出凸包，判斷是否和線相交即可我們求出與高速公路相近和近似相反的向量，判斷連線是否與這條公路相交即可。 */ #include <cstdio> #include <algorithm> #include <cmath> #include <vector> using namespace std; double EPS=1e-10; const double PI=acos(-1.0); double add(double a,double b){if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;return a+b; } struct P{double x,y;P(){}P(double x,double y):x(x),y(y){}P operator + (P p){return P(add(x,p.x),add(y,p.y));}P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}P operator * (double d){return P(x*d,y*d);}double dot(P p){return add(x*p.x,y*p.y);} //點積double det(P p){return add(x*p.y,-y*p.x);} //叉積 }; bool cmp_x(const P& p,const P& q){if(p.x!=q.x)return p.x<q.x;return p.y<q.y; } vector<P> convex_hull(P* ps,int n){sort(ps,ps+n,cmp_x);int k=0;vector<P> qs(n*2);for(int i=0;i<n;i++){while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;qs[k++]=ps[i];}for(int i=n-2,t=k;i>=0;i--){while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;qs[k++]=ps[i];}qs.resize(k-1);return qs; } double dist(P p,P q){return sqrt((p-q).dot(p-q));} double normalize(double r){if(r<-PI/2.0+EPS)r+=PI*2;return r; } double atan2(const P& p){return normalize(atan2(p.y, p.x)); } bool double_cmp(double a,double b){return a+EPS<b; } const int MAX_N=100010; int N,n; P ps[MAX_N]; double as[MAX_N]; void solve(){for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);vector<P> chs;if(N>1){chs=convex_hull(ps,N);n=chs.size();chs.push_back(chs[0]);}for(int i=0;i<n;i++)as[i]=atan2(chs[i+1]-chs[i]);sort(as,as+n,double_cmp);P p1,p2;while(~scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y)){if(N<2){puts("GOOD");continue;}int x=upper_bound(as,as+n,atan2(p2-p1),double_cmp)-as;int y=upper_bound(as,as+n,atan2(p1-p2),double_cmp)-as;puts((((p2-p1).det(chs[x]-p1)*(p2-p1).det(chs[y]-p1)>-EPS))?"GOOD":"BAD");} } int main(){while(~scanf("%d",&N))solve();return 0; }

POJ 3608：Bridge Across Islands

/*題目大意：求出兩個凸包之間的最短距離題解：我們先找到一個凸包的上頂點和一個凸包的下定點，以這兩個點為起點向下一個點畫線，做旋轉卡殼，答案一定包含在這個過程中 */ #include <cstdio> #include <algorithm> #include <cmath> #include <vector> using namespace std; double EPS=1e-10; const double INF=0x3F3F3F3F; const double PI=acos(-1.0); double add(double a,double b){if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;return a+b; } struct P{double x,y;P(){}P(double x,double y):x(x),y(y){}P operator + (P p){return P(add(x,p.x),add(y,p.y));}P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}P operator * (double d){return P(x*d,y*d);}double dot(P p){return add(x*p.x,y*p.y);} //點積double det(P p){return add(x*p.y,-y*p.x);} //叉積 }; bool cmp_y(const P& p,const P& q){if(p.y!=q.y)return p.y<q.y;return p.x<q.x; } double dist(P p,P q){return sqrt((p-q).dot(p-q));} double cross(P a, P b,P c){return(b-a).det(c-a);} double multi(P a,P b,P c){return(b-a).dot(c-a);} // 點到線段距離 double point_to_line(P a,P b,P c){if(dist(a,b)<EPS)return dist(b,c);if(multi(a,b,c)<-EPS)return dist(a,c);if(multi(b,a,c)<-EPS)return dist(b,c);return fabs(cross(a,b,c)/dist(a,b)); } // 線段到線段距離 double line_to_line(P A,P B,P C,P D){double a=point_to_line(A,B,C);double b=point_to_line(A,B,D);double c=point_to_line(C,D,A);double d=point_to_line(C,D,B);return min(min(a,b),min(c,d)); } void anticlockwise_sort(P* p,int N){for(int i=0;i<N-2;i++){double tmp=cross(p[i],p[i+1],p[i+2]);if(tmp>EPS)return;else if(tmp<-EPS){reverse(p,p+N);return;}} } const int MAX_N=10000; int n,m; P ps[MAX_N],qs[MAX_N]; void solve(){for(int i=0;i<n;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);for(int i=0;i<m;i++)scanf("%lf%lf",&qs[i].x,&qs[i].y);anticlockwise_sort(ps,n);anticlockwise_sort(qs,m);int i=0,j=0;for(int k=0;k<n;k++)if(!cmp_y(ps[i],ps[k]))i=k;for(int k=0;k<n;k++)if(cmp_y(qs[j],qs[k]))j=k;double res=INF;ps[n]=ps[0]; qs[m]=qs[0];for(int k=0;k<n;k++){while(cross(ps[i+1],qs[j+1],ps[i])-cross(ps[i+1],qs[j],ps[i])>EPS)j=(j+1)%m;res=min(res,line_to_line(ps[i],ps[i+1],qs[j],qs[j+1]));i=(i+1)%n;}printf("%.5lf\n",res); } int main(){while(~scanf("%d%d",&n,&m)&&n+m)solve();return 0; }

POJ 2079：Triangle

/*題目大意：給出一些點，求出能組成的最大面積的三角形題解：最大三角形一定位于凸包上，因此我們先求凸包，再在凸包上計算，因為三角形在枚舉了一條固定邊之后，圖形面積隨著另一個點的位置變換先變大后變小因此我們發現面積遞減之后就移動固定邊。 */ #include <cstdio> #include <algorithm> #include <cmath> #include <vector> using namespace std; double EPS=1e-10; const double PI=acos(-1.0); double add(double a,double b){if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;return a+b; } struct P{double x,y;P(){}P(double x,double y):x(x),y(y){}P operator + (P p){return P(add(x,p.x),add(y,p.y));}P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}P operator * (double d){return P(x*d,y*d);}double dot(P p){return add(x*p.x,y*p.y);} //點積double det(P p){return add(x*p.y,-y*p.x);} //叉積 }; bool cmp_x(const P& p,const P& q){if(p.x!=q.x)return p.x<q.x;return p.y<q.y; } vector<P> convex_hull(P* ps,int n){sort(ps,ps+n,cmp_x);int k=0;vector<P> qs(n*2);for(int i=0;i<n;i++){while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;qs[k++]=ps[i];}for(int i=n-2,t=k;i>=0;i--){while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;qs[k++]=ps[i];}qs.resize(k-1);return qs; } double cross(P A,P B,P C){return(B-A).det(C-A);} const int MAX_N=50010; int N; P ps[MAX_N]; void solve(){for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);vector<P> qs=convex_hull(ps,N);N=qs.size(); int ans=0;for(int i=1;i<(N+1)/2;i++){ //枚舉跨度 int p1=(i+1)%N;for(int p3=0;p3<N;p3++){int p2=(p3+i)%N;int prev=abs(cross(qs[p3],qs[p2],qs[p1]));for(++p1;p1!=p2&&p1!=p3;++p1){if(p1==N)p1=0;int cur=abs(cross(qs[p3],qs[p2],qs[p1]));ans=max(ans,prev);if(cur<=prev)break;prev=cur;}--p1;if(p1==-1)p1+=N;}}printf("%d.%s\n",ans/2,ans%2==1?"50":"00"); } int main(){while(~scanf("%d",&N)&&N>0)solve();return 0; }

POJ 3246：Game

/*題目大意:給出一些點，請刪去一個點，使得包圍這些點用的線長最短題解：去掉的點肯定是凸包上的點，所以枚舉凸包上的點去掉，再計算面積即可。 */ #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <cstring> using namespace std; struct P{int x,y;int id;P(){}P(double x,double y):x(x),y(y){}P operator + (P p){return P(x+p.x,y+p.y);}P operator - (P p){return P(x-p.x,y-p.y);}P operator * (double d){return P(x*d,y*d);}int dot(P p){return x*p.x+y*p.y;} //點積int det(P p){return x*p.y-y*p.x;} //叉積 }; bool cmp_x(const P& p,const P& q){if(p.x!=q.x)return p.x<q.x;return p.y<q.y; } vector<P> convex_hull(P* ps,int n){sort(ps,ps+n,cmp_x);int k=0;vector<P> qs(n*2);for(int i=0;i<n;i++){while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;qs[k++]=ps[i];}for(int i=n-2,t=k;i>=0;i--){while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;qs[k++]=ps[i];}qs.resize(k-1);return qs; } int cross(P a, P b,P c){return(b-a).det(c-a);} int compute_area(P A,P B,P C){int res=cross(A,B,C);if(res<0){return -res;}return res; } int compute_area(const vector<P>& ps){int total=0;for(int i=2;i<ps.size();i++){total+=compute_area(ps[0],ps[i-1],ps[i]);}return total; } const int MAX_N=100010; int N; P p[MAX_N],q[MAX_N]; void solve(){for(int i=0;i<N;i++){scanf("%d%d",&p[i].x,&p[i].y);p[i].id=i;}memcpy(q,p,N*sizeof(P));vector<P> ps=convex_hull(p,N);int ans=0x3f3f3f3f;for(int i=0;i<ps.size();i++){memcpy(p,q,N*sizeof(P));swap(p[ps[i].id],p[N-1]);ans=min(ans,compute_area(convex_hull(p,N-1)));}printf("%d.%s\n",ans/2,ans%2==1?"50":"00"); } int main(){while(~scanf("%d",&N),N)solve();return 0; }

?

轉載于:https://www.cnblogs.com/forever97/p/6561153.html

總結

以上是生活随笔為你收集整理的挑战程序设计竞赛 3.6 与平面和空间打交道的计算几何的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。