 /**//*
题意:给出一些正方形的边长,方法如图 问最后从上往下看能看到的矩形
我是先计算出最后正方的位置 , 这个可通过调整
一开始让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
搜索
最新评论

|
|