Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 229 | Accepted: 152 |
Description
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.
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.
Input
Output
Sample Input
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
Sample Output
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 <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define EPS 1e-10
#define N 1010 int dcmp(double x)
{
if(fabs(x)<EPS) return ;
return x<?-:;
}
struct Point
{
double x,y;
Point (){}
Point (double x,double y):x(x),y(y){}
Point operator - (Point p){
return Point(x-p.x,y-p.y);
}
double operator * (Point p){
return x*p.x+y*p.y;
}
double operator ^ (Point p){
return x*p.y-y*p.x;
}
bool operator < (const Point &p)const
{
if(y!=p.y) return y>p.y;
return x<p.x;
}
};
struct Line
{
Point s,e;
Line (){}
Line (Point s,Point e):s(s),e(e){}
};
bool PointOnSeg(Line l,Point p)
{
return dcmp((l.s-p)^(l.e-p))== && dcmp((l.s-p)*(l.e-p))<=;
}
int PointInConvexPoly(Point p[],Point q,int n)
{
for(int i=;i<n;i++){
if(dcmp((p[i]-q)^(p[(i+)%n]-q))>) return -;
if(PointOnSeg(Line(p[i],p[(i+)%n]),q)) return ;
}
return ;
}
int main()
{
int n;
int T,iCase;
Point p[];
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&iCase,&n);
double mxx,mix,mxy,miy;
mix=miy=INF;
mxx=mxy=-INF;
for(int i=;i<n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
mix=min(mix,p[i].x);
mxx=max(mxx,p[i].x);
miy=min(miy,p[i].y);
mxy=max(mxy,p[i].y);
}
int k=;
Point q[];
for(int i=mix;i<=mxx;i++){
for(int j=miy;j<=mxy;j++){
if(PointInConvexPoly(p,Point(i,j),n)==){
q[k++]=Point(i,j);
}
}
}
if(k==){
printf("%d 0\n",iCase);
continue;
}
sort(q,q+k);
int i,j,cnt=;
for(i=;i<k;i++) if(q[i].y!=q[i-].y) cnt++;
printf("%d %d\n",iCase,cnt);
for(i=;i<k;i++){
printf("%g %g",q[i].y,q[i].x);
for(j=i+;j<k;j++){
if(q[j].y!=q[i].y) break;
}
printf(" %g",q[j-].x);
printf("\n");
i=j-;
}
}
return ;
}