首页 > ACM题库 > HDU-杭电 > HDU 2872-Another Snake[解题报告]HOJ
2014
02-17

HDU 2872-Another Snake[解题报告]HOJ

Another Snake

问题描述 :

In this problem, we consider a classic video game called ‘Snake’. If you don’t know what is, I’ll let all-round wikipedia explains to you.
The player controls a long, thin creature, resembling a snake, which roams around on a bordered plane, picking up food (or some other item), trying to avoid hitting its own tail or the "walls" that surround the playing area. Each time the snake eats a piece of food, its tail grows longer, making the game increasingly difficult. The user controls the direction of the snake’s head (up, down, left, or right), and the snake’s body follows. The player cannot stop the snake from moving while the game is in progress.
–Wikipedia
Recently, we downloaded a new version of Snake. This snake has infinity length, started at (0, 0). Snake can change direction counter-clockwise only at certain points, freely from 0 degree to 180 degrees (include 0 degree but not 180 degrees). Because Snake has infinity length, the total length appeared on screen grows longer and longer, that means, the tail of Snake always locates at (0, 0). The Snake wants to know the maximum pieces of food can be eaten. And, Snake will continue going forward after eating the last one, and it cannot hit itself.

Consider the condition below, after eat the last piece D, the Snake will hit himself. This condition should be considered illegal.

输入:

The input contains multiple cases.
For each test case, the first line has one integer n(n<=15), indicates the number of points on the plane.
Following n lines, each line contains two integers, x and y describe the position of a piece of food.

输出:

The input contains multiple cases.
For each test case, the first line has one integer n(n<=15), indicates the number of points on the plane.
Following n lines, each line contains two integers, x and y describe the position of a piece of food.

样例输入:

2
0 1
1 0
10
0 1
-1 0
0 -1
1 2
2 -2
-2 1
1 0
-1 -1
1 3
-3 -2

样例输出:

2
10
Hint
Hint

#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

#define N 20
#define inf 0x3f3f3f3f
#define eps 1e-16
#define LL long long
#define Pi acos(-1)

struct Point{
 double x, y;
};

Point p[N], pnt[N];
int res, t, n;
bool mark[N];

double dot(double x1, double y1, double x2, double y2){
 return x1 * x2 + y1 * y2;
}

double cross(double x1, double y1, double x2, double y2){
 return x1 * y2 - x2 * y1;
}

int dblcmp(double n) {
 if (fabs(n) < eps) {
 return 0;
 } else {
 return n > 0 ? +1 : -1;
 }
}

bool segXseg(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4){
 double c1 = cross(x1 - x3, y1 - y3, x2 - x3, y2 - y3);
 double c2 = cross(x1 - x4, y1 - y4, x2 - x4, y2 - y4);
 double c3 = cross(x3 - x1, y3 - y1, x4 - x1, y4 - y1);
 double c4 = cross(x3 - x2, y3 - y2, x4 - x2, y4 - y2);
// if (fabs(c1) < eps && fabs(c2) < eps && fabs(c3) < eps && fabs(c4) < eps) return false;
 if (c1 * c2 < -eps && c3 * c4 < -eps) return true;
 if ((dblcmp(c1) == 0 && dblcmp(dot(x1 - x3, y1 - y3, x2 - x3, y2 - y3)) <= 0) ||
 (dblcmp(c2) == 0 && dblcmp(dot(x1 - x4, y1 - y4, x2 - x4, y2 - y4)) <= 0) ||
 (dblcmp(c3) == 0 && dblcmp(dot(x3 - x1, y3 - y1, x4 - x1, y4 - y1)) <= 0) ||
 (dblcmp(c4) == 0 && dblcmp(dot(x3 - x2, y3 - y2, x4 - x2, y4 - y2)) <= 0)) {
 return true;
 }
 return false;
}

bool ok(int k){
 double c = cross(pnt[t].x - pnt[t - 1].x, pnt[t].y - pnt[t - 1].y, p[k].x - pnt[t].x, p[k].y - pnt[t].y);
 double d = dot(pnt[t].x - pnt[t - 1].x, pnt[t].y - pnt[t - 1].y, p[k].x - pnt[t].x, p[k].y - pnt[t].y);
 if (!((c > eps || (fabs(c) < eps && d > 0)))){
 return false;
 }

 Point tmp;
 for (int i = 0; i <= t - 2; ++i){
 tmp.x = pnt[t].x + (p[k].x - pnt[t].x) * 100000000.0;
 tmp.y = pnt[t].y + (p[k].y - pnt[t].y) * 100000000.0;
 if (segXseg(pnt[i].x, pnt[i].y, pnt[i + 1].x, pnt[i + 1].y, pnt[t].x, pnt[t].y, tmp.x, tmp.y)){
 return false;
 }
 }
 return true;
}

void DFS(){
 int i;
 for (i = 1; i <= n; ++i){
 if (res == n) return ;
 if (!mark[i] && (t < 1 || ok(i))){
 pnt[++t] = p[i];
 mark[i] = true;
 if (t > res) res = t;
 DFS();
 t--;
 mark[i] = false;
 }
 }
}

int main(){
 int i;
 while (scanf("%d", &n) != EOF){
 for (i = 1; i <= n; ++i){
 scanf("%lf%lf", &p[i].x, &p[i].y);
 }
 memset(mark, false, sizeof(mark));
 pnt[0].x = pnt[0].y = 0;
 t = 0;
 res = 0;
 DFS();
 printf("%d\n", res);
 }
 return 0;
}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }