首页 > ACM题库 > HDU-杭电 > HDU 3286-Interior Points of Lattice Polygons-模拟-[解题报告]HOJ
2014
03-13

HDU 3286-Interior Points of Lattice Polygons-模拟-[解题报告]HOJ

Interior Points of Lattice Polygons

问题描述 :

A lattice point is a point with integer coordinates. A lattice polygon is a polygon with all vertices lattice points.
Convex Hull of Lattice Points

The lattice points on the boundary of the polygon are boundary points (open dots in the figure above) and the points inside and not on the polygon are interior points (filled in dots in the figure above).

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. Note that any line between two points inside (and not on the boundary of) the polygon is entirely inside (and not on the boundary of) the polygon.

The interior points of a convex lattice polygon on any horizontal line form a single segment from a leftmost point to a rightmost point (which may be the same). Note that there may be no interior points (A), or only one (B), or isolated points (C) as shown in the figures below.

Convex Hull of Lattice Points

Write a program that reads the vertices of a convex lattice polygon in standard order and outputs the interior points as a list of horizontal line segments. 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.

输入:

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 vertices N, (3 ≤ N ≤ 50), of the polygon. The remaining lines in the data set contain the vertices, one per line in standard order. Each line contains the decimal integer x coordinate, a space and the decimal integer y coordinate.

输出:

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 vertices N, (3 ≤ N ≤ 50), of the polygon. The remaining lines in the data set contain the vertices, one per line in standard order. Each line contains the decimal integer x coordinate, a space and the decimal integer y coordinate.

样例输入:

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

样例输出:

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

暴力不解释

#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>
#include<limits.h>
using namespace std;

#define LL long long
#define pi acos(-1)
#define FRE freopen("a.txt","r",stdin)
#define MAX INT_MAX
#define MIN INT_MIN
#define eps 1e-6
#define N 55
struct point{
    int x,y;
}p[N];
int n;
int ans[10010][3];
int tot;
void gao(int y){
    int i,j;
    double m[5];
    int cnt=0;
    for(i=1;i<=n;i++){
        if(p[i].y==y && p[i-1].y==y)return ;

        if(p[i].y==y)m[cnt++]=(double)p[i].x;

        if(p[i-1].y==y)m[cnt++]=(double)p[i-1].x;

        if((p[i-1].y<y && p[i].y>y) || (p[i-1].y>y && p[i].y<y))
        m[cnt++]=1.0*(y-p[i].y)*(p[i].x-p[i-1].x)/(p[i].y-p[i-1].y)+p[i].x;
    }
    int s,t;

    if(!cnt)return ;
    double minm=MAX;
    double maxm=MIN;
    for(i=0;i<cnt;i++)
    {
        minm=min(minm,m[i]);
        maxm=max(maxm,m[i]);
    }
    s=floor(minm)+1;//返回小于或者等于指定表达式的最大整数
    t=ceil(maxm)-1;//返回大于或者等于指定表达式的最小整数 
    if(s>t)return ;
    ans[tot][0]=y;
    ans[tot][1]=s;
    ans[tot][2]=t;
    tot++;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int ca;
        scanf("%d%d",&ca,&n);
        int i,j;
        int minm=MAX;
        int maxm=MIN;
        for(i=1;i<=n;i++){
            scanf("%d%d",&p[i].x,&p[i].y);
            minm=min(minm,p[i].y);
            maxm=max(maxm,p[i].y);
        }
        p[0].x=p[n].x;
        p[0].y=p[n].y;
        tot=0;
        for(i=maxm-1;i>=minm+1;i--){
            gao(i);
        }
        printf("%d %d\n",ca,tot);
        for(i=0;i<tot;i++)
        printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
    }
    return 0;
}

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


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。