/*
題意:在一個矩形區域內,有n條線段,線段的端點是在矩形邊上的
有一個特殊點treasure,問從這個點到矩形邊的最少經過的線段(實際穿過線段時只能穿過中點)
枚舉矩形外的每一段的中點與treasure連成一條線段link,判斷這條線段經過的線段數目即可
因為圍成的區域都是凸的,link闖過的線段必須要經過,不能繞過去
要理解穿過最少門的意思
參考http://hi.baidu.com/ackyclouday/blog/item/8c8665d299e94286a1ec9cfc.html
先按照極角排序,方便做很多!!
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 110;
const double EPS = 1e-8;
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)
{
x = _x;
y = _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;
}
};
//OA*OB = |OA|*|OB|*cos(AOB)
inline double dot(Point O , Point A , Point B)
{
Point OA = A - O;
Point OB = B - O;
return OA.x * OB.x + OA.y * OB.y;
}
//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 inSegment(Point pt , Segment seg)
{
if(sign(cross(pt,seg.a, seg.b)))return 0;
int ans = sign(dot(pt , seg.a , seg.b));
return ans == 0 ? 2 : ans < 0;
}
//線段和線段相交情況: 0:不相交, 1:規范相交, 2:交于端點 , 3:有重合部分
int across(Segment AB, Segment CD)//快速排斥實驗 + 相互跨立(是相互)
{
if( max(AB.a.x , AB.b.x) < min(CD.a.x , CD.b.x) || max(AB.a.y , AB.b.y) < min(CD.a.y , CD.b.y)
|| max(CD.a.x , CD.b.x) < min(AB.a.x , AB.b.x) || max(CD.a.y , CD.b.y) < min(AB.a.y , AB.b.y) )
return 0;
int AB_CD = sign(cross(AB.a , AB.b , CD.a)) * sign(cross(AB.a , AB.b , CD.b));
int CD_AB = sign(cross(CD.a , CD.b , AB.a)) * sign(cross(CD.a , CD.b , AB.b));
//有重合部分
if(AB_CD == 0 && CD_AB == 0 && (inSegment(AB.a , CD) == 1 || inSegment(AB.b , CD) == 1 ) )return 3;
if(AB_CD < 0)//CD跨立AB
{
return CD_AB ==0 ? 2: CD_AB < 0;
}
else if(AB_CD == 0)return CD_AB <= 0 ? 2 : 0;
return 0;
}
int n;
Segment seg[MAXN];
Point treasure , pt[MAXN*10];
inline double dist(Point A , Point B)
{
double x = A.x - B.x;
double y = A.y - B.y;
return sqrt(x*x+y*y);
}
bool cmp(const Point &A , const Point &B)
{
Point zero = Point(0,0);
int ans = sign(cross(zero,A,B));
if(ans == 0 )return dist(zero,A) + EPS < dist(zero,B);
return ans > 0;
}
int solve()
{
int ans = n+1 , cnt = 0;
for(int i = 0; i < n; i++)
{
pt[cnt++] = seg[i].a;
pt[cnt++] = seg[i].b;
}
pt[cnt++] = Point(0,0);
pt[cnt++] = Point(100,100);
pt[cnt++] = Point(100,0);
pt[cnt++] = Point(0,100);
sort(pt,pt+cnt,cmp);//先按照極角排序,方便做很多!!
for(int i = 1; i < cnt; i++)
{
Point center = Point((pt[i].x+pt[i-1].x)/2 , (pt[i].y+pt[i-1].y)/2);
Segment link = Segment(treasure , center);
int tot = 0;
for(int j = 0; j<n ;j++)
{
if(across(link,seg[j]))tot++;
}
if(tot<ans)ans = tot;
}
return ans + 1;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("in","r",stdin);
#endif
double x1,y1,x2,y2;
while( ~scanf("%d",&n) )
{
for(int i = 0; i<n; i++)
{
scanf("%lf%lf%lf%lf",&seg[i].a.x,&seg[i].a.y,&seg[i].b.x,&seg[i].b.y);
}
scanf("%lf%lf",&treasure.x,&treasure.y);
printf("Number of doors = %d\n",solve());
}
return 0;
}
題意:在一個矩形區域內,有n條線段,線段的端點是在矩形邊上的
有一個特殊點treasure,問從這個點到矩形邊的最少經過的線段(實際穿過線段時只能穿過中點)
枚舉矩形外的每一段的中點與treasure連成一條線段link,判斷這條線段經過的線段數目即可
因為圍成的區域都是凸的,link闖過的線段必須要經過,不能繞過去
要理解穿過最少門的意思
參考http://hi.baidu.com/ackyclouday/blog/item/8c8665d299e94286a1ec9cfc.html
先按照極角排序,方便做很多!!
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 110;
const double EPS = 1e-8;
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)
{
x = _x;
y = _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;
}
};
//OA*OB = |OA|*|OB|*cos(AOB)
inline double dot(Point O , Point A , Point B)
{
Point OA = A - O;
Point OB = B - O;
return OA.x * OB.x + OA.y * OB.y;
}
//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 inSegment(Point pt , Segment seg)
{
if(sign(cross(pt,seg.a, seg.b)))return 0;
int ans = sign(dot(pt , seg.a , seg.b));
return ans == 0 ? 2 : ans < 0;
}
//線段和線段相交情況: 0:不相交, 1:規范相交, 2:交于端點 , 3:有重合部分
int across(Segment AB, Segment CD)//快速排斥實驗 + 相互跨立(是相互)
{
if( max(AB.a.x , AB.b.x) < min(CD.a.x , CD.b.x) || max(AB.a.y , AB.b.y) < min(CD.a.y , CD.b.y)
|| max(CD.a.x , CD.b.x) < min(AB.a.x , AB.b.x) || max(CD.a.y , CD.b.y) < min(AB.a.y , AB.b.y) )
return 0;
int AB_CD = sign(cross(AB.a , AB.b , CD.a)) * sign(cross(AB.a , AB.b , CD.b));
int CD_AB = sign(cross(CD.a , CD.b , AB.a)) * sign(cross(CD.a , CD.b , AB.b));
//有重合部分
if(AB_CD == 0 && CD_AB == 0 && (inSegment(AB.a , CD) == 1 || inSegment(AB.b , CD) == 1 ) )return 3;
if(AB_CD < 0)//CD跨立AB
{
return CD_AB ==0 ? 2: CD_AB < 0;
}
else if(AB_CD == 0)return CD_AB <= 0 ? 2 : 0;
return 0;
}
int n;
Segment seg[MAXN];
Point treasure , pt[MAXN*10];
inline double dist(Point A , Point B)
{
double x = A.x - B.x;
double y = A.y - B.y;
return sqrt(x*x+y*y);
}
bool cmp(const Point &A , const Point &B)
{
Point zero = Point(0,0);
int ans = sign(cross(zero,A,B));
if(ans == 0 )return dist(zero,A) + EPS < dist(zero,B);
return ans > 0;
}
int solve()
{
int ans = n+1 , cnt = 0;
for(int i = 0; i < n; i++)
{
pt[cnt++] = seg[i].a;
pt[cnt++] = seg[i].b;
}
pt[cnt++] = Point(0,0);
pt[cnt++] = Point(100,100);
pt[cnt++] = Point(100,0);
pt[cnt++] = Point(0,100);
sort(pt,pt+cnt,cmp);//先按照極角排序,方便做很多!!
for(int i = 1; i < cnt; i++)
{
Point center = Point((pt[i].x+pt[i-1].x)/2 , (pt[i].y+pt[i-1].y)/2);
Segment link = Segment(treasure , center);
int tot = 0;
for(int j = 0; j<n ;j++)
{
if(across(link,seg[j]))tot++;
}
if(tot<ans)ans = tot;
}
return ans + 1;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("in","r",stdin);
#endif
double x1,y1,x2,y2;
while( ~scanf("%d",&n) )
{
for(int i = 0; i<n; i++)
{
scanf("%lf%lf%lf%lf",&seg[i].a.x,&seg[i].a.y,&seg[i].b.x,&seg[i].b.y);
}
scanf("%lf%lf",&treasure.x,&treasure.y);
printf("Number of doors = %d\n",solve());
}
return 0;
}
這個排序應該是想排出來按逆時針圍繞原點的順序來的吧
但是對于這道題來說
矩形位于原點上方那條豎著的邊,貌似順序就反過來了吧(極角相同,按dist排)
雖然這個影響不大。
但是排好之后
從這個豎著的邊之前的 那一個點 和豎著的邊的任何點(除了左上角頂點)構成的線段貌似就不屬于矩形邊上的線段了吧?
這樣寫cmp應該是才是對的(估計題目數據太水,沒有測出你的問題)
bool cmp(const Point &A , const Point &B)
{
Point O = Point(-1.0 , -1.0); //設置成(0,0)會有問題
int ans = sign(cross(O , A , B));
if (fix_double(A.y) == 0 && fix_double(B.y) == 0)
return dist(O , A) + EPS < dist(O , B);
else if (fix_double(A.x) == 0 && fix_double(B.x) == 0)
return dist(O , A) + EPS > dist(O , B);
else
return ans > 0;
} //cmp
還有一個地方我有點疑惑。(主要覺得你的模版寫得挺好的,我就來花了點時間研究一下)
<pre>
int across(Segment AB, Segment CD)//快速排斥實驗 + 相互跨立(是相互)
{
if( max(AB.a.x , AB.b.x) < min(CD.a.x , CD.b.x) || max(AB.a.y , AB.b.y) < min(CD.a.y , CD.b.y)
|| max(CD.a.x , CD.b.x) < min(AB.a.x , AB.b.x) || max(CD.a.y , CD.b.y) < min(AB.a.y , AB.b.y) )
return 0;
int AB_CD = sign(cross(AB.a , AB.b , CD.a)) * sign(cross(AB.a , AB.b , CD.b));
int CD_AB = sign(cross(CD.a , CD.b , AB.a)) * sign(cross(CD.a , CD.b , AB.b));
//有重合部分
if(AB_CD == 0 && CD_AB == 0 && (inSegment(AB.a , CD) == 1 || inSegment(AB.b , CD) == 1 ) )return 3;
if(AB_CD < 0)//CD跨立AB
{
return CD_AB ==0 ? 2: CD_AB < 0;
}
else if(AB_CD == 0)return CD_AB <= 0 ? 2 : 0;
return 0;
}
</pre>
這段代碼中 return 3 那個情況我覺得還沒有考慮到兩個線段共線并且共享一個端點,我覺得這個地方應該改成
if (AB_CD == 0 && CD_AB == 0 && (inSegment(AB.a , CD) || inSegment(AB.b , CD) )) return 3;
:)
你寫的排序好像不對啊。。。