 /**//*
題意:給出一些正方形的邊長(zhǎng),方法如圖 問(wèn)最后從上往下看能看到的矩形
我是先計(jì)算出最后正方的位置 , 這個(gè)可通過(guò)調(diào)整
一開(kāi)始讓s[i] = 0
然后檢查會(huì)不會(huì)跟j(j<i)矛盾,矛盾的話調(diào)整

然后再暴力,從左往右掃,看直線是否與線段相交

如果_INF要參與運(yùn)算的話,注意不要太大
有可能 _INF * EPS != 0
跟EPS有關(guān)吧,如EPS = 1e-8 的話 _INF < 1e5

事先f(wàn)ix_double()一下的話,會(huì)減少一些問(wèn)題,而且INF還能開(kāi)大點(diǎn)
*/
#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 應(yīng)該以后都沒(méi)問(wèn)題了
 {
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);
}
};

//這里沒(méi)考慮線段、直線 退化成點(diǎn)的情況
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的逆時(shí)針?lè)较?右手螺旋)
//=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:規(guī)范相交, 2:不規(guī)范相交(交于端點(diǎn)或重合)
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;
}

//計(jì)算交點(diǎn)前需先判斷是否相交 直線可以是平行于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--)//調(diào)整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;
}
|
|
常用鏈接
隨筆分類(lèi)
Links
搜索
最新評(píng)論

|
|