首页 > ACM题库 > HDU-杭电 > HDU 3685-Rotational Painting-计算几何-[解题报告]HOJ
2014
11-30

HDU 3685-Rotational Painting-计算几何-[解题报告]HOJ

Rotational Painting

问题描述 :

Josh Lyman is a gifted painter. One of his great works is a glass painting. He creates some well-designed lines on one side of a thick and polygonal glass, and renders it by some special dyes. The most fantastic thing is that it can generate different meaningful paintings by rotating the glass. This method of design is called “Rotational Painting (RP)” which is created by Josh himself.

You are a fan of Josh and you bought this glass at the astronomical sum of money. Since the glass is thick enough to put erectly on the table, you want to know in total how many ways you can put it so that you can enjoy as many as possible different paintings hiding on the glass. We assume that material of the glass is uniformly distributed. If you can put it erectly and stably in any ways on the table, you can enjoy it.

More specifically, if the polygonal glass is like the polygon in Figure 1, you have just two ways to put it on the table, since all the other ways are not stable. However, the glass like the polygon in Figure 2 has three ways to be appreciated.

Gunshots

Pay attention to the cases in Figure 3. We consider that those glasses are not stable.
Gunshots

输入:

The input file contains several test cases. The first line of the file contains an integer T representing the number of test cases.

For each test case, the first line is an integer n representing the number of lines of the polygon. (3<=n<=50000). Then n lines follow. The ith line contains two real number xi and yi representing a point of the polygon. (xi, yi) to (xi+1, yi+1) represents a edge of the polygon (1<=i<n), and (xn,yn) to (x1, y1) also represents a edge of the polygon. The input data insures that the polygon is not self-crossed.

输出:

The input file contains several test cases. The first line of the file contains an integer T representing the number of test cases.

For each test case, the first line is an integer n representing the number of lines of the polygon. (3<=n<=50000). Then n lines follow. The ith line contains two real number xi and yi representing a point of the polygon. (xi, yi) to (xi+1, yi+1) represents a edge of the polygon (1<=i<n), and (xn,yn) to (x1, y1) also represents a edge of the polygon. The input data insures that the polygon is not self-crossed.

样例输入:

2
4
0 0
100 0
99 1
1 1
6
0 0
0 10
1 10
1 1
10 1
10 0

样例输出:

2
3
Hint
The sample test cases can be demonstrated by Figure 1 and Figure 2 in Description part.

下午和队友一起做了下杭州赛区的比赛题,结果被虐了,只过了三题,两个队友没一会儿就开始打酱油。。。。实在受不了。

 

这道题裸的计算几何,求出多边形的重心,求重凸包,然后直接判断重心到凸包各点的投影是否在线段上,注意这里不用求出投影直接用点积即可,队友看错题WA了一次,我看了下图发现90的时候是不稳的。。。。到此整题就理论AC了,只要代码稳,可以轻松拿下。

 

我的代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX=50100;
const double oo=1e10;
const double eps=1e-8;

struct Point{
double x,y;
double angle,dis;

Point(){

}
Point(double x,double y):x(x),y(y){

}
};

struct Line{
Point p1,p2;

Line(){

}
Line(Point p1,Point p2):p1(p1),p2(p2){

}
};

typedef vector<Point> Polygon;
typedef vector<Point> Points;

bool ZERO(double x){
return fabs(x)<eps;
}

bool ZERO(Point p){
return ZERO(p.x)&&ZERO(p.y);
}

bool EQ(double x,double y){
return fabs(x-y)<eps;
}

bool NEQ(double x,double y){
return fabs(x-y)>=eps;
}

bool LT(double x,double y){
return NEQ(x,y)&&x<y;
}

bool GT(double x,double y){
return NEQ(x,y)&&x>y;
}

bool LEQ(double x,double y){
return EQ(x,y)||x<y;
}

bool GEQ(double x,double y){
return EQ(x,y)||x>y;
}

double sqr(double x){
return x*x;
}

bool operator==(const Point& p1,const Point& p2){
return EQ(p1.x,p2.x)&&EQ(p1.y,p2.y);
}

bool operator!=(const Point& p1,const Point& p2){
return NEQ(p1.x,p2.x)||NEQ(p1.y,p2.y);
}

bool operator<(const Point& p1,const Point& p2){
if(NEQ(p1.x,p2.x)){
return p1.x<p2.x;
}else{
return p1.y<p2.y;
}
}

Point operator+(const Point& p1,const Point& p2){
return Point(p1.x+p2.x,p1.y+p2.y);
}

Point operator-(const Point& p1,const Point& p2){
return Point(p1.x-p2.x,p1.y-p2.y);
}

double operator*(const Point& p1,const Point& p2){
return p1.x*p2.y-p1.y*p2.x;
}

double operator&(const Point& p1,const Point& p2){
return p1.x*p2.x+p1.y*p2.y;
}

double Norm(const Point& p){
return sqrt(sqr(p.x)+sqr(p.y));
}

bool comp(const Point& left,const Point& right){
if(EQ(left.angle,right.angle)){
return left.dis<right.dis;
}else{
return left.angle<right.angle;
}
}

void Scan(Points& points,Polygon& result){
int i,k,n;
Point p;
n=points.size();
result.clear();

if(n<3){
result=points;
return;
}

k=0;
for(i=1;i<n;i++){
if(EQ(points[i].y,points[k].y)){
if(points[i].x<=points[k].x){
k=i;
}
}else if(points[i].y<points[k].y){
k=i;
}
}
swap(points[0],points[k]);

for(i=1;i<n;i++){
points[i].angle=atan2(points[i].y-points[0].y,points[i].x-points[0].x);
points[i].dis=Norm(points[i]-points[0]);
}
sort(points.begin()+1,points.end(),comp);
result.push_back(points[0]);
for(i=1;i<n;i++){
if((i+1<n)&&EQ(points[i].angle,points[i+1].angle)){
continue;
}
if(result.size()>=3){
p=result[result.size()-2];
while(GEQ((points[i]-p)*(result.back()-p),0)){
result.pop_back();
p=result[result.size()-2];
}
}
result.push_back(points[i]);
}
}

Point center(const Polygon& poly){
Point p,p0,p1,p2,p3;
double m,m0;

p1=poly[0];
p2=poly[1];
p.x=p.y=m=0;

for(int i=2;i<(int)poly.size();i++){
p3=poly[i];
p0.x=(p1.x+p2.x+p3.x)/3.0;
p0.y=(p1.y+p2.y+p3.y)/3.0;
m0=p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x;
if(ZERO(m+m0)){
m0+=eps;
}
p.x=(m*p.x+m0*p0.x)/(m+m0);
p.y=(m*p.y+m0*p0.y)/(m+m0);
m+=m0;
p2=p3;
}

return p;
}

bool isconter(const Points pts){
double res=0.0;
int n=pts.size();
for(int i=0;i<n;i++){
res+=(pts[i]*pts[(i+1)%n]);
}
return res>0;
}

bool check(const Point& p,const Line& l){
return LT((l.p1-p)&(l.p2-l.p1),0)&<((l.p2-p)&(l.p1-l.p2),0);
}

Points pts,poly;

int main(){
int t;
int n,ret;
Point p;

scanf("%d",&t);
while(t--){
scanf("%d",&n);
ret=0;
pts.clear();
for(int i=0;i<n;i++){
scanf("%lf%lf",&p.x,&p.y);
pts.push_back(p);
}
if(!isconter(pts)){
reverse(pts.begin(),pts.end());
}
p=center(pts);
Scan(pts,poly);
n=poly.size();
poly.push_back(poly[0]);
for(int i=0;i<n;i++){
if(check(p,Line(poly[i],poly[i+1]))){
ret++;
}
}

printf("%d/n",ret);
}

return 0;
}

 

 

参考:http://blog.csdn.net/lyhypacm/article/details/5978389


  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?