题意：

题意：一张图上给出n个点的坐标(xi,yi)，其中xi，yi均为正整数。记这n个点中，拥有最小y的点为A，你开始从点(0, yA)开始走向点A，然后，你可以随意选择径直走去另外的点，但必须满足一下3个条件：

1：只能向左转向（也可直走）。

2：走过的路径为留下一条红色的轨迹。

3：不能越过这条红色的轨迹。

问你最多能到达几个点，并且按到达的顺序输出各个点的标号。

 

 

题解：

叉积 + dfs

易证：按照一定的顺序，每次选择当前左转角度最小的点（相等则选距离最近的点），

必能按条件遍历所有的点。

 1 #include<cstdio>

 2 #include<cstring>

 3 #include<cmath>

 4 #include<iostream>

 5 #include<algorithm>

 6 #include<

set>

 7 #include<map>

 8 #include<queue>

 9 #include<vector>

10 #include<

string>

11 

#define Min(a,b) a<b?a:b

12 

#define Max(a,b) a>b?a:b

13 

#define CL(a,num) memset(a,num,sizeof(a));

14 

#define maxn  60

15 

#define eps  1e-8

16 

#define inf 100000000

17 

#define mx 1<<60

18 

#define ll   __int64

19 

using 

namespace std;

20 

21 

struct point

22 {

23     

int id ;

24     

int ord ;

25     

double x;

26     

double y;

27 }p[maxn];

28 

bool vis[maxn] ;

29 

double ans ;

30 

int  n,num ;

31 

int det(

int x1,

int y1,

int x2,

int y2)

32  {

33      

return x1*y2 - x2*y1;

34  }

35  

int cross(point a,point b,point c)

36  {

37      

return det(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);

38  }

39 

double dis(point a,point b)

40 {

41     

double  x1 = a.x;

42     

double y1 = a.y;

43     

double x2 = b.x;

44     

double y2 = b.y ;

45     

return   (x2 - x1 )*(x2 - x1) + (y2-y1)*(y2 - y1);

46 }

47 

void dfs(

int pre,

int num)

48 {

49 

50     

if(num == n) 

return ;

51     

int mi = 

1;

52     

while(vis[mi])mi++;

53     

for(

int i = mi + 

1 ;i <= n;i++)

54     {

55         

if(vis[i])

continue ;

56         

double w = cross(p[pre],p[mi],p[i]);

57         

if(w  < - eps) mi = i;

58         

if(w < fabs(eps) && dis(p[pre],p[i]) < dis(p[pre],p[mi])) mi = i;

59     }

60     p[mi].ord = num + 

1;

61 

62     vis[mi] = 

true ;

63     dfs(mi,num + 

1) ;

64 }

65 

bool cmp(point a,point b)

66 {

67     

return  a.ord < b.ord ;

68 }

69 

int main()

70 {

71     

int i,j;

72     

//

freopen("data.txt","r",stdin);

73 

    

int  t;

74     scanf(

"

%d

",&t);

75 

76     

while(t--)

77     {

78         scanf(

"

%d

",&n);

79         CL(vis,

false );

80         

int mi = inf ;

81         

for(i = 

1 ; i<= n;i++)

82         {

83             scanf(

"

%d%lf%lf

",&p[i].id,&p[i].x,&p[i].y);

84             

if(mi == inf||p[mi].y > p[i].y) mi =  i;

85         }

86         vis[mi] = 

true ;

87 

88         p[mi].ord = 

1 ;

89         dfs(mi,

1);

90         sort(p + 

1 ,p + 

1 + n,cmp);

91         printf(

"

%d

",n);

92         

for(i = 

1;i <=n;i++)

93         {

94 

95             printf(

"

 %d

",p[i].id) ;

96         }

97         printf(

"

\n

");

98     }

99 }