题目大意:给一些散列点然后初始点是坐标最下面最左面的点,然后只能往左走,求出来最多可以经过多少个点,把序号输出出来。
 
分析:先求出来初始的点,然后不断排序找出来最近的凸点....复杂度是 n^2*log(n)。。。。不多点很少,所以随意玩。
 
代码如下:
=====================================================================================================================
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std; const int MAXN = ;
const double EPS = 1e-; struct Point
{
double x, y;
int id;
Point(double x=, double y=):x(x),y(y){}
Point operator - (const Point &tmp) const{
return Point(x-tmp.x, y-tmp.y);
}
double operator *(const Point &tmp) const{
return x*tmp.x + y*tmp.y;
}
double operator ^(const Point &tmp) const{
return x*tmp.y - y*tmp.x;
}
};
double Dist(Point a, Point b)
{
return sqrt((a-b)*(a-b));
}
Point p[MAXN];
int ki; bool cmp(Point a, Point b)
{
double t = (a-p[ki]) ^ (b-p[ki]); if(fabs(t) < EPS)
return Dist(p[ki], a) < Dist(p[ki], b);
return t > EPS;
} int main()
{
int T; scanf("%d", &T); while(T--)
{
int i, N; scanf("%d", &N); for(int i=; i<N; i++)
{
scanf("%d%lf%lf", &p[i].id, &p[i].x, &p[i].y);
if(p[i].y < p[].y || (p[i].y==p[].y && p[i].x < p[].x))
swap(p[i], p[]);
} ki = ; for(i=; i<N; i++, ki++)
{
sort(p+i, p+N, cmp);
} printf("%d", N);
for(i=; i<N; i++)
printf(" %d", p[i].id);
printf("\n");
} return ;
}
05-11 15:26