几何题小测

发表于 | 更新于 | 分类于

POJ2007

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
#include<cstdio>
#include<algorithm>
using namespace std;
struct Point {
    int  x,y;
}a[100];
typedef Point Vector;
int cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}
bool cmp(Vector a,Vector b){
    return cross(a,b)>=0;
}
int main(){
    int x,y;
    int tot=0;
    while(~scanf("%d%d",&x,&y)){
        a[++tot].x=x;
        a[tot].y=y;
    }
    sort(a+2,a+tot+1,cmp);
    for(int i=1;i<=tot;i++){
        printf("(%d,%d)\n",a[i].x,a[i].y);
    }
    //system("pause");
}

POJ2624

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
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct Point {
    double  x,y;
    Point(double x=0,double y=0):x(x),y(y){}
}a[100];
typedef Point Vector;
Vector operator - (Point A,Point 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);
}
const double eps=1e-10;
// int dcmp(double x){//精度问题
// 	if(fabs(x)<eps) return 0;
// 	else return x<0?-1:1;
// }
bool operator ==(const Point& a,const Point& b){
	return (a.x-b.x)==0&&(a.y-b.y)==0;
}
int main(){
    while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a[1].x,&a[1].y,&a[2].x,&a[2].y,&a[3].x,&a[3].y,&a[4].x,&a[4].y)){
        Point ans;
        if(a[1]==a[3]){
            ans=a[2]-a[1]+a[4]-a[1]+a[1];
        }
        else if(a[1]==a[4]){
            ans=a[2]-a[1]+a[3]-a[1]+a[1];
        }
        else if(a[2]==a[3]){    
            ans=a[1]-a[2]+a[4]-a[2]+a[2];
        }
        else if(a[2]==a[4]){
            ans=a[1]-a[2]+a[3]-a[2]+a[2];
        }
        printf("%.3lf %.3lf\n",ans.x,ans.y);
    }
}

POJ1569

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
56
57
58
59
60
61
62
63
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int n;
struct Point {
    double  x,y;
    Point(double x=0,double y=0):x(x),y(y){}
}a[100];
typedef Point Vector;
Vector operator - (Point A,Point 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)==0&&(a.y-b.y)==0;
}
double cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}
double Area(Point A,Point B,Point C){
	return fabs(cross(B-A,C-A));
}
bool check(int i,int j,int k){
    double area1=Area(a[i],a[j],a[k]);
    for(int ii=1;ii<=n;ii++){
        if(ii!=i&&ii!=j&&ii!=k){
            double sum0=Area(a[ii],a[i],a[j])+Area(a[ii],a[i],a[k])+Area(a[ii],a[j],a[k]);
            double sum1=Area(a[i],a[j],a[k]);
            if(sum0==sum1) return 0;
        }
    }
    return 1;
}
int main(){
    while(~scanf("%d",&n)&&n){
        char c;
        for(int i=1;i<=n;i++){
            cin>>c;
            scanf("%lf%lf",&a[i].x,&a[i].y);
        }
        double ans=0;
        int ans1,ans2,ans3;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                for(int k=j+1;k<=n;k++){
                    double area1=Area(a[i],a[j],a[k]);
                    if(check(i,j,k)){
                        double area1=Area(a[i],a[j],a[k]);
                        if(ans<=fabs(area1)){
                            ans=area1;
                            ans1=i,ans2=j,ans3=k;
                        }
                    }
                }
            }
        }
        printf("%c%c%c\n",ans1-1+'A',ans2-1+'A',ans3-1+'A');
    }
}

POJ3304

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
56
57
58
59
60
61
62
63
64
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int n;
struct Point {
    double  x,y;
    Point(double x=0,double y=0):x(x),y(y){}
}s[100],e[100];
typedef Point Vector;
Vector operator - (Point A,Point 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)==0&&(a.y-b.y)==0;
}
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;
}
const double eps=1e-10;
int sgn(double x){
    if(fabs(x) < eps)return 0;
    if(x < 0) return -1;
    return 1;
}
int Seg_inter_line(Point a1,Point a2,Point b1,Point b2){
    return Cross(a1-b1,a2-b1)*Cross(a1-b2,a2-b2)<=0;
}
bool check(Point ss,Point ee){
    if(Dot(ss-ee,ss-ee) == 0 )return false;
    for(int i = 1;i <= n;i++){
        if(Seg_inter_line(ss,ee,s[i],e[i]) == false)
            return false;
    }
    return true;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf%lf",&s[i].x,&s[i].y,&e[i].x,&e[i].y);
        }
        int flag=0;
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++)
                if(check(s[i],e[i])||check(s[i],s[j])||check(s[i],e[j])||check(e[i],e[j])||check(e[i],s[j])||check(s[j],e[j])){
                    flag=1;
                    break;
                }
          
        if(flag||n==1) printf("Yes!\n");
        else printf("No!\n");
    }
    //system("pause");
}

POJ1113

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
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;
const double pi=acos(-1.0);
struct Point {
    double x,y;
    Point (double x=0,double y=0):x(x),y(y){}
    bool operator <(const  Point &A){
        return x==A.x?y<A.y:x<A.x;
    }
    bool operator ==(const Point &A){
        return x==A.y&&y==A.y;
    }
    Point operator -(const Point &A){
        return Point(x-A.x,y-A.y);
    }
}a[maxn],ch[maxn];
typedef Point Vector;
int Cross(Point A,Point B){
    return A.x*B.y-A.y*B.x;
}
int ConvexHull(Point *p,int n,Point *ch){
    int m=0;
    for(int i=0;i<n;i++){
        while(m>1&&Cross(ch[m-1]-ch[m-2],a[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],a[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}
double Dot(Vector A,Vector B){
	return A.x*B.x+A.y*B.y;
}
double Length(Vector A){
	return sqrt(Dot(A,A));
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    sort(a,a+n);
    int len=ConvexHull(a,n,ch);
    double ans=0;
    for(int i=1;i<=len;i++){
        ans+=Length(ch[i]-ch[i-1]);
    }
    ans+=2*pi*m;
    printf("%.0lf\n",ans);

    //system("pause");
}