/**//* 题意:给出一些正方形的边长,方法如图 问最后从上往下看能看到的矩形 我是先计算出最后正方的位置 , 这个可通过调整 一开始让s[i] = 0 然后检查会不会跟j(j<i)矛盾,矛盾的话调整
然后再暴力,从左往右扫,看直线是否与线段相交
如果_INF要参与运算的话,注意不要太大 有可能 _INF * EPS != 0 跟EPS有关吧,如EPS = 1e-8 的话 _INF < 1e5
事先fix_double()一下的话,会减少一些问题,而且INF还能开大点 */ #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue>
using namespace std;
const int MAXN = 110; const double EPS = 1e-8; const double sqrt2 = sqrt(2.0);
inline double fix_double(double x) { return fabs(x)<EPS ? 0.0 : x; }
inline int sign(double x) { return x<-EPS?-1:x>EPS; }
struct Point { double x,y; Point(){} Point(double _x , double _y)//这里有fix_double 应该以后都没问题了 { x = fix_double(_x); y = fix_double(_y); } bool operator == (const Point B)const { return sign(x-B.x)==0 && sign(y-B.y)==0; } Point operator - (const Point B)const { return Point(x-B.x , y-B.y); } };
//这里没考虑线段、直线 退化成点的情况 struct Segment { Point a,b; Segment(){} Segment(Point _a,Point _b) { a = _a; b = _b; } };
struct Line { Point a,b; double ia , ib , ic;//iax + iby + ic = 0 Line(){} Line(Point _a , Point _b) { a = _a; b = _b; } void make()//(y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 { ia = b.y - a.y; ib = a.x - b.x; ic = b.x*a.y - a.x*b.y; //if(sign(ia)<0)ia = -ia , ib = -ib , ic = -ic; } };
//OA×OB = |OA|*|OB|*sin(AOB) //>0 OB在OA的逆时针方向(右手螺旋) //=0 OB跟OA共线 inline double cross(Point O , Point A , Point B) { Point OA = A - O; Point OB = B - O; return OA.x * OB.y - OB.x * OA.y; }
//线段和直线相交情况: 0:不相交, 1:规范相交, 2:不规范相交(交于端点或重合) int across(Segment seg, Line line)//判断线段与直线相交 只需判断线段是否跨立直线即可 { int ans = sign(cross(line.a,line.b,seg.a)) * sign(cross(line.a,line.b,seg.b)); return ans == 0 ? 2 : ans < 0; }
//计算交点前需先判断是否相交 直线可以是平行于y轴的 Point intersect(Line LA , Line LB) { LA.make(); LB.make(); double a1 = LA.ia , b1 = LA.ib , c1 = LA.ic; double a2 = LB.ia , b2 = LB.ib , c2 = LB.ic; double x = (c1*b2 - b1*c2)/(a2*b1-a1*b2); double y; if(sign(b1)) y = -(a1*x + c1)/b1; else y = -(a2*x + c2)/b2; return Point(x,y); }
Point intersect(Segment seg , Line line) { Line _line = Line(seg.a , seg.b); return intersect(_line,line); }
double a[100] , s[100]; bool vi[100];
int main() { #ifdef ONLINE_JUDGE #else freopen("in","r",stdin); #endif
for( int n; scanf("%d",&n) , n ;) { vector<pair<int,Segment> > vt; double xleft = 1e10; double xright = -1e10; for(int i = 0; i < n; i++) { scanf( "%lf" , &a[i] ); vi[i] = 0; s[i] = 0.0; for(int j = i-1; j>=0 ;j--)//调整s[i] 分a[i]<a[j] a[i]>=a[j]讨论 { double _s; if(a[i] < a[j]) _s = s[j] + sqrt2*a[i]; else _s = s[j] + sqrt2*a[j]; s[i] = max(s[i],_s); } Point mid = Point(s[i],sqrt2*a[i]); Point left = Point(s[i]-a[i]/sqrt2,a[i]/sqrt2); Point right = Point(s[i]+a[i]/sqrt2,a[i]/sqrt2); vt.push_back( make_pair(i, Segment(left,mid)) ); vt.push_back( make_pair(i, Segment(mid,right)) ); xleft = min(xleft , left.x); xright = max(xright , right.x); }
vector<int>ans; for(double x = xleft ; x - EPS < xright ; x += 0.01) { Line line = Line(Point(x,0) , Point(x,1e10)); double y; int id = -1; for(int i = 0 ; i < vt.size() ; i++) { Segment seg = vt[i].second; if(across(seg,line)) { Point pt = intersect(seg,line); if(id == -1 || y < pt.y)id = vt[i].first , y = pt.y; } } if(id != -1 && !vi[id]) { ans.push_back(id); vi[id] = true; } } sort(ans.begin(),ans.end()); for(int i = 0; i < ans.size(); i++) { if(i)putchar(' '); printf("%d",ans[i]+1); } puts(""); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|