首页 > ACM题库 > HDU-杭电 > HDU 3471-England vs Germany[解题报告]HOJ
2014
03-31

HDU 3471-England vs Germany[解题报告]HOJ

England vs Germany

问题描述 :

The big fight between England and Germany was destroyed by the guy called Larrionda. England could have made a tie of 2:2. But that poor guy disqualified Lampard’s wonderful goal. The ball passed through the goal line by half a meter, however, Larrionda turned a blind eye to this goal.
As a fan of Three Lion Regimen, silentsky want to develop a system which uses sensors to get the information to check if it scored or not.

The information includes a point as the location of ball, a vector as the velocity and a cuboid as the goal.

Chinese Paper Folding

输入:

The first line gives an integer t (t<=10000) indicating the number of test cases.
For each case:
The first line gives three real numbers x, y , z, indicating a point to represent the ball.
The second line gives three real numbers a, b, c. indicates a vector to represent the velocity.
The following 8 lines give 8 points according the sequence A, B, C, D, E, F, G, H as is shown in the figure.
Absolute value of all real numbers are smaller than 10000.
It is guaranteed that the initial location of the ball is not inside the goal.

输出:

The first line gives an integer t (t<=10000) indicating the number of test cases.
For each case:
The first line gives three real numbers x, y , z, indicating a point to represent the ball.
The second line gives three real numbers a, b, c. indicates a vector to represent the velocity.
The following 8 lines give 8 points according the sequence A, B, C, D, E, F, G, H as is shown in the figure.
Absolute value of all real numbers are smaller than 10000.
It is guaranteed that the initial location of the ball is not inside the goal.

样例输入:

1
20 0 5 
-10 5 0 
10 0 10
10 10 10
10 10 0 
10 0 0 
0 0 10 
0 10 10 
0 10 0
0 0 0 

样例输出:

Case 1: Stupid Larrionda!!!

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

#define abs(x) ((x)>=0?(x):-(x))
#define i64 long long
#define u32 unsigned int
#define u64 unsigned long long
#define clr(x,y) memset(x,y,sizeof(x))
#define CLR(x) x.clear()
#define ph(x) push(x)
#define pb(x) push_back(x)
#define Len(x) x.length()
#define SZ(x) x.size()
#define PI acos(-1.0)
#define sqr(x) ((x)*(x))
#define MP(x,y) make_pair(x,y)
#define EPS 1e-4

#define FOR0(i,x) for(i=0;i<x;i++)
#define FOR1(i,x) for(i=1;i<=x;i++)
#define FOR(i,a,b) for(i=a;i<=b;i++)
#define FORL0(i,a) for(i=a;i>=0;i--)
#define FORL1(i,a) for(i=a;i>=1;i--)
#define FORL(i,a,b)for(i=a;i>=b;i--)

#define rush() int CC;for(scanf("%d",&CC);CC--;)
#define Rush(n) while(scanf("%d",&n)!=-1)
using namespace std;

void RD(int &x){scanf("%d",&x);}
void RD(i64 &x){scanf("%lld",&x);}
void RD(u64 &x){scanf("%I64u",&x);}
void RD(u32 &x){scanf("%u",&x);}
void RD(double &x){scanf("%lf",&x);}
void RD(int &x,int &y){scanf("%d%d",&x,&y);}
void RD(i64 &x,i64 &y){scanf("%lld%lld",&x,&y);}
void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}
void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}
void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void RD(i64 &x,i64 &y,i64 &z){scanf("%lld%lld%lld",&x,&y,&z);}
void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}
void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}
void RD(char &x){x=getchar();}
void RD(char *s){scanf("%s",s);}
void RD(string &s){cin>>s;}

void PR(int x) {printf("%d\n",x);}
void PR(int x,int y) {printf("%d %d\n",x,y);}
void PR(i64 x) {printf("%lld\n",x);}
void PR(i64 x,i64 y) {printf("%lld %lld\n",x,y);}
void PR(u32 x) {printf("%u\n",x);}
void PR(u64 x) {printf("%llu\n",x);}
void PR(double x) {printf("%.2lf\n",x);}
void PR(char x) {printf("%c\n",x);}
void PR(char *x) {printf("%s\n",x);}
void PR(string x) {cout<<x<<endl;}

const int mod=10007;
const i64 inf=((i64)1)<<40;
const double dinf=1000000000000000000.0;
const int INF=100000000;
const int N=200005;

int sgn(double x)
{
 if(x>EPS) return 1;
 if(x<-EPS) return -1;
 return 0;
}

struct point3
{
 double x,y,z;
 
 point3(){}
 point3(double _x,double _y,double _z)
 {
 x=_x;
 y=_y;
 z=_z;
 }
 
 void get()
 {
 RD(x); RD(y); RD(z);
 }
 
 point3 operator+(point3 a)
 {
 return point3(x+a.x,y+a.y,z+a.z);
 }
 
 point3 operator-(point3 a)
 {
 return point3(x-a.x,y-a.y,z-a.z);
 }
 
 point3 operator*(point3 a)
 {
 return point3(y*a.z-z*a.y,z*a.x-x*a.z,x*a.y-y*a.x);
 }
 
 point3 operator*(double t)
 {
 return point3(x*t,y*t,z*t);
 }
 
 double operator^(point3 a)
 {
 return x*a.x+y*a.y+z*a.z;
 }
 
 double len()
 {
 return sqrt(x*x+y*y+z*z);
 }
};

point3 S,v,a,b,c,d,e,f,g,h;

point3 lineCrossPlane(point3 p,point3 q,point3 a,point3 b,point3 c)
{
 point3 k=(c-b)*(a-b);
 double t=(k^(a-p))/(k^(q-p));
 return p+((q-p)*t);
}

double len(point3 a)
{
 return a.len();
}

int inside(point3 p,point3 a,point3 b,point3 c,point3 d)
{
 double S=len(a-b)*len(c-b);
 double x1=len((p-a)*(p-b));
 double x2=len((p-b)*(p-c));
 double x3=len((p-c)*(p-d));
 double x4=len((p-d)*(p-a));
 if(!sgn(x1)||!sgn(x2)||!sgn(x3)||!sgn(x4)) return 0;
 return sgn(S-(x1+x2+x3+x4)*0.5)==0;
}

int main()
{
 int num=0;
 rush()
 {
 S.get(); v.get();
 a.get(); b.get(); c.get(); d.get();
 e.get(); f.get(); g.get(); h.get();
 point3 k=(a-d)*(c-d);
 printf("Case %d: ",++num);
 if(!sgn(len(v))||(v^k)<=0||(k^(S-d))>0)
 {
 puts("Intelligent Larrionda!!!");
 continue;
 }
 point3 p=lineCrossPlane(S,S+v,a,b,c);
 if(inside(p,a,b,c,d)) puts("Stupid Larrionda!!!");
 else puts("Intelligent Larrionda!!!");
 }
}

  1. #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;
    }

  2. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  4. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。