首页 > ACM题库 > HDU-杭电 > HDU 3285-Convex Hull of Lattice Points-凸包问题-[解题报告]HOJ
2014
03-13

HDU 3285-Convex Hull of Lattice Points-凸包问题-[解题报告]HOJ

Convex Hull of Lattice Points

问题描述 :

A lattice point is a point with integer coordinates. A lattice polygon is a polygon with all vertices lattice points.

A polygon is convex if any line segment between two points of the polygon is inside (or on the boundary of) the polygon. Equivalently, the interior angle at each polygon vertex is less than 180 degrees.

For a set S, of lattice points, the convex hull is the smallest convex (lattice) polygon which contains all points of the set. (The vertices of the convex hull must be members of the set of lattice points). If all the points are on a single straight line, the convex hull will be a line segment (a degenerate polygon � see rightmost diagram below). In the diagrams below, the points of the set are indicated by solid dots, the vertices of the convex hull by X’s and the convex hull is drawn connecting the vertices.
Note that not all points on the convex hull polygon are vertices.

Adjacent Bit Counts

The vertices of a lattice polygon are in standard order if:
a) The first vertex is the one with the largest y value. If two vertices have the same y value, the one with the smaller x value is the first.
b) Vertices are given in clockwise order around the polygon.

Write a program that reads a set of lattice points and outputs the vertices of the convex hull of the points in standard order.

输入:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by a decimal integer giving the number of points N, (3 ≤ N ≤ 50), in the set. The remaining lines in the data set contain the points in the set, at most 5 points per line (the last line may have fewer). Each point consists of 2 space separated decimal integer values representing the x and y coordinates
respectively.

输出:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by a decimal integer giving the number of points N, (3 ≤ N ≤ 50), in the set. The remaining lines in the data set contain the points in the set, at most 5 points per line (the last line may have fewer). Each point consists of 2 space separated decimal integer values representing the x and y coordinates
respectively.

样例输入:

4
1 25
2 1 7 1 1 2 9 2 1 3
10 3 1 4 10 4 1 5 10 5
2 6 10 6 2 7 9 7 3 8
8 8 4 9 7 9 6 2 3 3
5 4 7 5 8 6 4 6 3 7
2 30
3 9 6 9 3 8 9 8 3 7
12 7 2 6 12 6 2 5 12 5
2 4 12 4 1 3 11 3 1 2
11 2 1 1 11 1 1 0 10 0
4 -1 10 -1 7 -2 10 -2 5 0
7 3 4 5 6 8 3 1 2 6
3 3
3 1 2 2 1 3
4 6
1 3 19 1 4 2 2 1 11 2
10 1

样例输出:

1 10
4 9
7 9
10 6
10 3
9 2
7 1
2 1
1 2
1 5
2 7
2 8
3 9
6 9
12 7
12 4
10 -2
7 -2
1 0
1 3
3 2
1 3
3 1
4 4
1 3
11 2
19 1
2 1

因为常规的凸包是逆时针存的,所以只要找出左上角的点,然后逆着回去就ok!原模板没判断共点情况,害得wa了n次!!!

#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<algorithm>
#include<queue>
#include<list>
#include<set>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stdio.h>
#include<ctype.h>
#include<iomanip>

using namespace std;

#define LL long long
#define pi acos(-1)
#define FRE freopen("a.txt","r",stdin)
#define INF 9999999999
#define eps 1e-6
#define N 55

struct point
{
    int x,y;
};
point p[N],cHull[N],p0,stck[N];

int m;//凸包顶点数
int n;//所有点数
//(b,a)x(c,a)
int cnt;
int cross(point a,point b,point c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}//<0则ac在ab的顺时针,需要顺时针拐

int dis(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
//极角从小到大排序
bool cmp(point a,point b)
{
    int t=cross(p0,a,b);
    return t>0||(t==0 && dis(p0,a)<dis(p0,b));
    //t>0即p0b在p0a的逆时针
}
void convexHull()
{
    int i,j,k;
    m=0;
    cnt=0;
    for(k=0,i=0;i<n;i++)
        if(p[i].y<p[k].y||(p[i].y==p[k].y && p[i].x<p[k].x) )
            k=i;
    p0=p[k];//基点
    p[k]=p[0];
    p[0]=p0;
    sort(p+1,p+n,cmp);
    stck[0]=p[0];
    stck[1]=p[1];/*
    int flag=0;
    if(cross(stck[0],stck[1],p[2])==0)
    {
        flag=1;
        stck[1]=p[2];
    }
    if(flag)i=3;
    else
    i=2;*/
    int top=1;
    for(i=2;i<n;i++)
    {
        while(top && cross(stck[top-1],stck[top],p[i])<=0)//就是这里!!!<=0啊
            {
                    top--;
            }
        stck[++top]=p[i];
    }
    m=top+1;
}
bool ccmp(point a,point b){
    if(a.y==b.y)return a.x<b.x;
    return a.y>b.y;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int ca;
        int i,j;
        scanf("%d%d",&ca,&n);
        for(i=0;i<n;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
        convexHull();
        int xx=stck[0].x,yy=stck[0].y;
        int tag=0;
        for(i=1;i<m;i++)
             if(stck[i].y>stck[tag].y || (stck[i].y==stck[tag].y && stck[i].x<stck[tag].x))
               tag=i;
        printf("%d %d\n",ca,m);
        for(i=tag;i>=0;i--)
        printf("%d %d\n",stck[i].x,stck[i].y);
        for(i=m-1;i>tag;i--)
        printf("%d %d\n",stck[i].x,stck[i].y);
    }
    return 0;
}

参考:http://blog.csdn.net/leolin_/article/details/6725520


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience