首页 > 代码库 > hdu 3685 10 杭州 现场 F - Rotational Painting 重心
hdu 3685 10 杭州 现场 F - Rotational Painting 重心
F - Rotational Painting
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64uAppoint description:
Description
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.
Pay attention to the cases in Figure 3. We consider that those glasses are not stable.
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.
Pay attention to the cases in Figure 3. We consider that those glasses are not stable.
Input
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 x i and y i representing a point of the polygon. (x i, y i) to (x i+1, y i+1) represents a edge of the polygon (1<=i<n), and (x n,y n) to (x 1, y 1) also represents a edge of the polygon. The input data insures that the polygon is not self-crossed.
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 x i and y i representing a point of the polygon. (x i, y i) to (x i+1, y i+1) represents a edge of the polygon (1<=i<n), and (x n,y n) to (x 1, y 1) also represents a edge of the polygon. The input data insures that the polygon is not self-crossed.
Output
For each test case, output a single integer number in a line representing the number of ways to put the polygonal glass stably on the table.
Sample Input
240 0100 099 11 160 00 101 101 110 110 0
Sample Output
23
Hint
The sample test cases can be demonstrated by Figure 1 and Figure 2 in Description part.
划分三角形求个重心,再把原来的多边形求个凸包拓展为凸多边形,对此时凸包每边做重心垂线,若垂足落在边内不包括中点就能以这条边稳定
#include <iostream>#include <cmath>#include <iomanip>#include <cstdio>#include <cstdlib>#include <vector>#include <algorithm>using namespace std;const int maxn=60100;const double eps=1e-10;double add(double a,double b){ if(abs(a+b)<eps*(abs(a)+abs(b))) return 0; return a+b;}struct point{ double x,y; point () {} point(double x,double y) : x(x),y(y){ } point operator + (point p){ return point(add(x,p.x),add(y,p.y)); } point operator - (point p){ return point(add(x,-p.x),add(y,-p.y)); } point operator * (double d){ return point(x*d,y*d); } double dot(point p){ return add(x*p.x,y*p.y); } double det(point p){ return add(x*p.y,-y*p.x); }} pi[maxn];int nn;bool on_seg(point p1,point p2,point q){ return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;}point intersection(point p1,point p2,point q1,point q2){ return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));}bool cmp_x(const point& p,const point& q){ if(p.x!=q.x) return p.x<q.x; return p.y<q.y;}vector<point> convex_hull(point * ps,int n){ sort(ps,ps+n,cmp_x); int k=0; //凸包的顶点数 vector<point> qs(n*2); for(int i=0;i<n;i++){ while(k>1&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0) k--; qs[k++]=ps[i]; } for(int i=n-2,t=k;i>=0;i--){ while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0) k--; qs[k++]=ps[i]; } qs.resize(k-1); return qs;}point gravity(point *p,int n){ double area=0; point center; center.x=0; center.y=0; for(int i=0;i<n-1;i++){ area+=(p[i].x*p[i+1].y-p[i+1].x*p[i].y)/2; center.x+=(p[i].x*p[i+1].y-p[i+1].x*p[i].y)*(p[i].x+p[i+1].x); center.y+=(p[i].x*p[i+1].y-p[i+1].x*p[i].y)*(p[i].y+p[i+1].y); } area+=(p[n-1].x*p[0].y-p[0].x*p[n-1].y)/2; center.x+=(p[n-1].x*p[0].y-p[0].x*p[n-1].y)*(p[n-1].x+p[0].x); center.y+=(p[n-1].x*p[0].y-p[0].x*p[n-1].y)*(p[n-1].y+p[0].y); center.x/=6*area; center.y/=6*area; return center;}bool judge(point cen,point ind1,point ind2){ point v=ind1-ind2; point w;w.x=v.y;w.y=-v.x; point u=ind2-cen; double t=w.det(u)/v.det(w); // printf("%.8f\n",t); if(t<1&&t>0)return true; return false;}void solve(){ vector<point> pp; point cen; cen=gravity(pi,nn); pp=convex_hull(pi,nn); int ans=0; for(int i=0;i<pp.size();i++){ if(judge(cen,pp[i],pp[(i+1)%pp.size()])){ ans++; } } printf("%d\n",ans); return ;}int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d",&nn); for(int i=0;i<nn;i++) scanf("%lf%lf",&pi[i].x,&pi[i].y); solve(); }}
hdu 3685 10 杭州 现场 F - Rotational Painting 重心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。