题意：
建立围墙将城堡围起来，要求围墙至少距离城堡L，拐角处用圆弧取代，求围墙的长度。
题解：
答案是凸包周长加上一个圆周长。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=1010;
const double PI=acos(-1.0);
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
Point in[MAXN],out[MAXN];
Vector operator +(Vector A,Vector B)
{
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
bool operator <(const Point& a,const Point &b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
int convexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++)
{
while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
double length(Vector A)
{
return sqrt(A.x*A.x+A.y*A.y);
}
double perimeter(Point *p,int n)
{
double len=0;
for(int i=0;i<n-1;i++)
{
len+=length(p[i+1]-p[i]);
}
len+=length(p[0]-p[n-1]);
return len;
}
int main()
{
int n,cnt;
double l,ans;
while(scanf("%d%lf",&n,&l)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&in[i].x,&in[i].y);
}
cnt=convexHull(in,n,out);
ans=perimeter(out,cnt);
printf("%.f\n",ans+2*PI*l);
}
}
B - Scrambled Polygon
题意：
给出一个多边形的起点和n-1个乱序的坐标点，要求从起点逆序输出左边点
题解：
用叉积进行排序
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=500000;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
Point s(0.0,0.0);
Point point[MAXN];
typedef Point Vector;
Vector operator -(Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
int cmp(Point a,Point b)
{
return cross(a-s,b-s)>0;
}
int main()
{
double x,y;
int cnt=0;
scanf("%lf%lf",&s.x,&s.y);
while(scanf("%lf%lf",&x,&y)!=EOF)
{
point[++cnt]=Point(x,y);
}
sort(point+1,point+1+cnt,cmp);
printf("(%.f,%.f)\n",s.x,s.y);
for(int i=1;i<=cnt;i++)
{
printf("(%.f,%.f)\n",point[i].x,point[i].y);
}
}
C - The Fortified Forest
待填坑！！！
待填坑！！！
待填坑！！！
E - Cows
题解：
求凸包面积再除以５０
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=10010;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
Point in[MAXN],out[MAXN];
bool operator <(const Point &a,const Point &b )
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
Vector operator -(Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
int convexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++)
{
while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
double polyArea(Point *p,int n)
{
double area=0.0;
for(int i=1;i<n-1;i++)
{
area+=cross(p[i]-p[0],p[i+1]-p[0]);
}
return area/2;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&in[i].x,&in[i].y);
}
int ans=convexHull(in,n,out);
double area=polyArea(out,ans);
int res=(int)(area/50);
printf("%d\n",res);
}
}
Separate Points
题意：
有黑白两种颜色的点，判断是否可以用一条直线划分成颜色一致的两部分(输入点无坐标相同的点,直线上不能有输入点)
题解：
分别求出黑点的凸包，再求出白点的凸包，如果两个凸包可以分离,那么可以用直线划分；
可以分离的充要条件是两个凸包的边界和内部没有公共部分（哪怕一个点也不行）
（一）任取一个黑点，判断是否在白凸包内部；如果是，则无解；否则，再取白点，判断是否在凸包的内部，如果是，则无解
（二）任取黑凸包的线段判断是否和白凸包的线段是否规范相交，如果是，则无解
以上两个条件都满足才可以划分点集
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=110;
const int INF=0x7fffffff;
const double EPS=1e-10;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
Point white[MAXN],black[MAXN],wout[MAXN],bout[MAXN];
typedef Point Vector;
Vector operator -(Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
bool operator <(const Point &a,const Point &b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
return A.x*B.x+A.y*B.y;
}
int convexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++)
{
while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
int dcmp(double val)
{
if(abs(val)<EPS) return 0;
else if(val>0) return 1;
else return -1;
}
bool isPointOnSegment(Point p,Point a,Point b)//点在线段上(不包括端点)
{
return cross(a-p,b-p)==0&&dot(a-p,b-p)<0;
}
bool segmentInterect(Point a1,Point a2,Point b1,Point b2)//规范相交
{
int c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1);
int c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
int isPointInPolygon(Point *ch,int n,Point p)//是否在多边形内部
{
int wn=0;
for(int i=0;i<n;i++)
{
if(isPointOnSegment(p,ch[i],ch[(i+1)%n])) return 1;
int k=dcmp(cross(ch[(i+1)%n]-ch[i],p-ch[i]));
int d1=dcmp(ch[i].y-p.y);
int d2=dcmp(ch[(i+1)%n].y-p.y);
if(k>0&&d1<=0&&d2>0) wn++;
if(k<0&&d2<=0&&d1>0) wn--;
}
if(wn) return 1;
else return 0;
}
int main()
{
int n,m,bct,wct;
while(scanf("%d%d",&n,&m)!=EOF,n+m)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&white[i].x,&white[i].y);
}
for(int i=0;i<m;i++)
{
scanf("%lf%lf",&black[i].x,&black[i].y);
}
wct=convexHull(white,n,wout);
bct=convexHull(black,m,bout);
bool flag=false;
for(int i=0;i<wct;i++)
{
if(isPointInPolygon(bout,bct,wout[i]))
{
flag=true;
break;
}
}
if(!flag)
{
for(int i=0;i<bct;i++)
{
if(isPointInPolygon(wout,wct,bout[i]))
{
flag=true;
break;
}
}
}
if(!flag)
{
for(int i=0;i<wct;i++)
{
if(flag) break;
for(int j=0;j<bct;j++)
{
if(segmentInterect(wout[i],wout[(i+1)%wct],bout[j],bout[(j+1)%bct]))
{
flag=true;
break;
}
}
}
}
if(flag) printf("NO\n");
else printf("YES\n");
}
return 0;
}
B - Shape of HDU
题意：
给定多边形的逆序节点，判断一个多边形是不是凸多边形
题解：
可以用相邻两边的旋转角来判断，逆时针取点，若存在点p1, p2, p3，矢边p1p2, 到p2p3，为顺时针旋转则此多边形为凹多边形,可以用叉积判断时针方向
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=50000;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
Point point[MAXN];
typedef Point Vector;
Vector operator +(Vector A,Vector B)
{
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF,n)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&point[i].x,&point[i].y);
}
bool flag=true;
for(int i=0;i<n-2;i++)
{
if(cross(point[i+1]-point[i],point[i+2]-point[i])<0)
{
flag=false;
break;
}
}
if(cross(point[n-1]-point[n-2],point[0]-point[n-1])<0) flag=false;
if(cross(point[0]-point[n-1],point[1]-point[0])<0) flag=false;
if(flag) printf("convex\n");
else printf("concave\n");
}
}
C - Surround the Trees
题意：
求凸包周长
题解：
这里比较坑的地方有，1个点的时候输出０，两个点的时候，凸包求出来是有两条边的，但是只需输出两点距离即可
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=110;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
Point in[MAXN],out[MAXN];
typedef Point Vector;
Vector operator +(Vector A,Vector B)
{
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator -(Vector A,Vector B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
bool operator <(const Point &a,const Point &b)
{
return a.x<b.x||(a.x==b.x&&(a.y<b.y));
}
int convexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++)
{
while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
double length(Vector A)
{
return sqrt(A.x*A.x+A.y*A.y);
}
double perimeter(Point *p,int n)
{
double len=0;
for(int i=0;i<n-1;i++)
{
len+=length(p[i+1]-p[i]);
}
len+=length(p[0]-p[n-1]);
return len;
}
int main()
{
int n,ans;
double len;
while(scanf("%d",&n)!=EOF,n)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&in[i].x,&in[i].y);
}
if(n==1)
{
printf("0.00\n");
continue;
}
else if(n==2)
{
printf("%.2f\n",length(in[1]-in[0]));
continue;
}
ans=convexHull(in,n,out);
len=perimeter(out,ans);
printf("%.2f\n",len);
}
}
网友评论