Training:计算几何基础

计算几何基础部分大部分题目只要有模板就能过了,下面的题也大都是贴模板过的。

HDU 1086:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17612
给出 n 条线段,求其中相交的对数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
struct Line{
double x1,y1,x2,y2;
}a[110];
bool solve(Line a,Line b){
if(((a.x1-b.x1)*(a.y2-b.y1)-(a.x2-b.x1)*(a.y1-b.y1))*((a.x1-b.x2)*(a.y2-b.y2)-(a.x2-b.x2)*(a.y1-b.y2))>0)return false;
if(((b.x1-a.x1)*(b.y2-a.y1)-(b.x2-a.x1)*(b.y1-a.y1))*((b.x1-a.x2)*(b.y2-a.y2)-(b.x2-a.x2)*(b.y1-a.y2))>0)return false;
return true;
}
int main(){
int n;
while(~scanf("%d",&n)&&n){
int cnt=0;
for(int i=0;i<n;++i)
scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
if(solve(a[i],a[j]))
++cnt;
printf("%d\n",cnt);
}
return 0;
}

HDU 1115:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=16214
按顺序给出多个点,求给出点的的重心坐标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
using namespace std;
const int maxn=1000010;
struct node{
double x,y;
}a[maxn];
node gravity(node *p, int n)
{
double area = 0;
node center;
center.x = 0;
center.y = 0;
for (int i = 0; i < n-1; i++)
{
area += (p[i].x*p[i+1].y - p[i+1].x*p[i].y)/2;
center.x += (p[i].x*p[i+1].y - p[i+1].x*p[i].y) * (p[i].x + p[i+1].x);
center.y += (p[i].x*p[i+1].y - p[i+1].x*p[i].y) * (p[i].y + p[i+1].y);
}
area += (p[n-1].x*p[0].y - p[0].x*p[n-1].y)/2;
center.x += (p[n-1].x*p[0].y - p[0].x*p[n-1].y) * (p[n-1].x + p[0].x);
center.y += (p[n-1].x*p[0].y - p[0].x*p[n-1].y) * (p[n-1].y + p[0].y);
center.x /= 6*area;
center.y /= 6*area;
return center;
}
int main(){
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
node ans=gravity(a,n);
printf("%.2lf %.2lf\n",ans.x,ans.y);
}
return 0;
}

HDU 2036:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17490
按顺序给出多个点的坐标,求所构成的凸多边形面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<cmath>
const int maxn=110;
struct point{
double x,y;
}a[maxn];
double area_polygon(int n,point* p){
double s1=0,s2=0;
for(int i=0;i<n;++i)
s1+=p[(i+1)%n].y*p[i].x,s2+=p[(i+1)%n].y*p[(i+2)%n].x;
return fabs(s1-s2)/2;
}
int main(){
int n;
while(~scanf("%d",&n)&&n){
for(int i=0;i<n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
printf("%.1lf\n",area_polygon(n,a));
}
return 0;
}

HDU 2108:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18631
按顺序给出多个点,判断形成的是凸多边形,还是凹多边形。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<cmath>
const int maxn=110;
struct point{
double x,y;
}a[maxn];
#define eps 1e-8
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
double xmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int is_convex(int n,point* p){
int i,s[3]={1,1,1};
for (i=0;i<n&&s[1]|s[2];i++)
s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0; return s[1]|s[2];
}
int main(){
int n;
while(~scanf("%d",&n)&&n){
for(int i=0;i<n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
puts(is_convex(n,a)?"convex":"concave");
}
return 0;
}

HDU 1392:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18630
给出多个点,求凸包的周长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=110;
struct point{
double x,y;
}a[maxn],b[maxn];
bool mult(point p0,point p1,point p2){
return (p1.x-p0.x)*(p2.y-p0.y)>=(p2.x-p0.x)*(p1.y-p0.y);
}
bool operator<(const point &p1,const point &p2){
return p1.y<p2.y||(p1.y==p2.y&&p1.x<p2.x);
}
int graham(point pnt[],int n,point res[]){
int i,len,top=1;
sort(pnt,pnt+n);
if(n==0) return 0;
res[0]=pnt[0];
if(n==1) return 1;
res[1]=pnt[1];
if(n==2) return 2;
res[2]=pnt[2];
for(i=2;i<n;i++){
while(top&&mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
len=top;res[++top]=pnt[n-2];
for(i=n-3;i>=0;i--){
while(top!=len&&mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
return top;
}
int main(){
int n;
while(~scanf("%d",&n)&&n){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
int k=graham(a,n,b);
double ans=0;
for(int i=0;i<k-1;++i)
ans+=sqrt((b[i].x-b[i+1].x)*(b[i].x-b[i+1].x)+(b[i].y-b[i+1].y)*(b[i].y-b[i+1].y));
if(k>2) ans+=sqrt((b[k-1].x-b[0].x)*(b[k-1].x-b[0].x)+(b[k-1].y-b[0].y)*(b[k-1].y-b[0].y));
printf("%.2lf\n",ans);
}
return 0;
}

HDU 1348:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=32007
求凸包每个顶点向外延伸半径为1的圆后所得图形的周长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
struct point{
double x,y;
}a[maxn],b[maxn];
bool mult(point p0,point p1,point p2){
return (p1.x-p0.x)*(p2.y-p0.y)>=(p2.x-p0.x)*(p1.y-p0.y);
}
bool operator<(const point &p1,const point &p2){
return p1.y<p2.y||(p1.y==p2.y&&p1.x<p2.x);
}
int graham(point pnt[],int n,point res[]){
int i,len,top=1;
sort(pnt,pnt+n);
if(n==0) return 0;
res[0]=pnt[0];
if(n==1) return 1;
res[1]=pnt[1];
if(n==2) return 2;
res[2]=pnt[2];
for(i=2;i<n;i++){
while(top&&mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
len=top;res[++top]=pnt[n-2];
for(i=n-3;i>=0;i--){
while(top!=len&&mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
return top;
}
int main(){
int t;scanf("%d",&t);
while(t--){
int n,l;scanf("%d%d",&n,&l);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
int k=graham(a,n,b);
double ans=0;
for(int i=0;i<k-1;++i)
ans+=sqrt((b[i].x-b[i+1].x)*(b[i].x-b[i+1].x)+(b[i].y-b[i+1].y)*(b[i].y-b[i+1].y));
if(k>2) ans+=sqrt((b[k-1].x-b[0].x)*(b[k-1].x-b[0].x)+(b[k-1].y-b[0].y)*(b[k-1].y-b[0].y));
ans+=2*acos(-1)*l;
printf("%.0lf\n",ans);
if(t) printf("\n");
}
return 0;
}

HDU 2150:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=31178
给出多条线段,判断有无相交线段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
struct Line{
double x1,y1,x2,y2;
Line(double x1=0,double y1=0,double x2=0,double y2=0):x1(x1),y1(y1),x2(x2),y2(y2){}
};
struct node{
int k;
Line l[110];
}a[33];
bool solve(Line a,Line b){
if(((a.x1-b.x1)*(a.y2-b.y1)-(a.x2-b.x1)*(a.y1-b.y1))*((a.x1-b.x2)*(a.y2-b.y2)-(a.x2-b.x2)*(a.y1-b.y2))>0)return false;
if(((b.x1-a.x1)*(b.y2-a.y1)-(b.x2-a.x1)*(b.y1-a.y1))*((b.x1-a.x2)*(b.y2-a.y2)-(b.x2-a.x2)*(b.y1-a.y2))>0)return false;
return true;
}
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=0;i<n;++i){
scanf("%d",&a[i].k);
--a[i].k;
double px1,py1;
scanf("%lf%lf",&px1,&py1);
for(int j=0;j<a[i].k;++j){
double x1,y1;
scanf("%lf%lf",&x1,&y1);
a[i].l[j]=Line(px1,py1,x1,y1);
px1=x1,py1=y1;
}
}
bool flag=false;
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
for(int k=0;k<a[i].k;++k)
for(int l=0;l<a[j].k;++l)
if(solve(a[i].l[k],a[j].l[l])) {flag=true;goto END;}
END:
printf("%s\n",flag?"Yes":"No");
}
return 0;
}

HDU 1558:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19356
给出多条线段,输出有几个连通块。判断线段相交之后,用并查集求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<string>
using namespace std;
const int maxn=1010;
int p[maxn],num[maxn];
struct Line{
double x1,y1,x2,y2;
Line(double x1=0,double y1=0,double x2=0,double y2=0):x1(x1),y1(y1),x2(x2),y2(y2){}
}a[maxn];
//有模板就是好!!!
bool solve(Line a,Line b){
if(((a.x1-b.x1)*(a.y2-b.y1)-(a.x2-b.x1)*(a.y1-b.y1))*((a.x1-b.x2)*(a.y2-b.y2)-(a.x2-b.x2)*(a.y1-b.y2))>0)return false;
if(((b.x1-a.x1)*(b.y2-a.y1)-(b.x2-a.x1)*(b.y1-a.y1))*((b.x1-a.x2)*(b.y2-a.y2)-(b.x2-a.x2)*(b.y1-a.y2))>0)return false;
return true;
}
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy) p[fx]=fy,num[fy]+=num[fx];
return;
}
int main(){
int t;cin>>t;
while(t--){
int n,cnt=0;cin>>n;
for(int i=0;i<n;++i){
string s;cin>>s;
if(s=="P"){
++cnt,p[cnt]=cnt,num[cnt]=1;
Line& k=a[cnt];
cin>>k.x1>>k.y1>>k.x2>>k.y2;
for(int j=1;j<cnt;++j){
if(find(j)!=find(cnt)&&solve(a[j],k))
merge(cnt,j);
}
}
else if(s=="Q"){
int k;cin>>k;
cout<<num[find(k)]<<endl;
}
}
if(t) cout<<endl;
}
return 0;
}

HDU 1785:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=30271
就是结构体重载运算符的题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<algorithm>
const int maxn=110;
struct node{
double x,y;
bool operator < (const node& rhs) const {
return x*rhs.y>rhs.x*y;
}
}a[maxn];
int main(){
int n;
while(~scanf("%d",&n)&&n>=0){
for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
std::sort(a,a+n);
for(int i=0;i<n;++i) printf("%.1lf %.1lf%c",a[i].x,a[i].y,i==n-1?'\n':' ');
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。

支付宝扫码领红包