07~11的比赛没怎么做，，真是辛苦sunkang了*^ ^*、、
唉。。可惜花了大把时间竟然没考过科目二，希望23号那一场可以考过> <！
A - Eight Queens
判断给出的解是不是八皇后的合法解。
<span style="font-size:18px;">#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
char Board[8][10];
bool flag;
bool ok(int x, int y)
{
if(x >= 8 || x < 0) return false;
if(y >= 8 || y < 0) return false;
return true;
}
int main()
{
// freopen("A.in", "r", stdin);
while(~scanf("%s", Board[0]))
{
flag = true;
for(int i = 1; i < 8; i++) scanf("%s", Board[i]);
for(int i = 0; i < 8; i++)
{
if(!flag) break;
bool ck = true;
for(int j = 0; j < 8; j++)
{
if(Board[i][j] == '*')
{
if(!ck) { flag = false; break; }
if( ck) ck = false;
}
}
}
for(int i = 0; i < 8; i++)
{
if(!flag) break;
bool ck = true;
for(int j = 0; j < 8; j++)
{
if(Board[j][i] == '*')
{
if(!ck) { flag = false; break; }
if( ck) ck = false;
}
}
}
for(int i = 0; i < 8; i++)
{
int x = i, y = 0;
bool ck = true;
for(int j = 0; j < 8 && ok(x, y); j++)
{
if(Board[x][y] == '*')
{
if(!ck) { flag = false; break; }
if( ck) ck = false;
}
x++, y++;
}
}
for(int i = 0; i < 8; i++)
{
int x = i, y = 0;
bool ck = true;
for(int j = 0; j < 8 && ok(x, y); j++)
{
if(Board[y][x] == '*')
{
if(!ck) { flag = false; break; }
if( ck) ck = false;
}
x++, y++;
}
}
for(int i = 7; i >= 0; i--)
{
int x = i, y = 0;
bool ck = true;
for(int j = 0; j < 8 && ok(x, y); j++)
{
if(Board[x][y] == '*')
{
if(!ck) { flag = false; break; }
if( ck) ck = false;
}
x--, y++;
}
}
for(int i = 7; i >= 0; i--)
{
int x = i, y = 0;
bool ck = true;
for(int j = 0; j < 8 && ok(x, y); j++)
{
if(Board[y][x] == '*')
{
if(!ck) { flag = false; break; }
if( ck) ck = false;
}
x--, y++;
}
}
if(flag) puts("valid");
else puts("invalid");
}
return 0;
}</span>
E - Human Cannonball Run
给出起始点和终点，和途中中各个大炮的位置。人跑步的速度是5m/s，大炮上膛加发射至50m（任意方向），需要2s。问从起点到终点，最短需要多长时间。
注意呀！起点必须要跑着去任意一个点。。。
<span style="font-size:18px;">#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 110
#define eps 1e-10
inline double sig(double x) { return (x > eps) - (x < -eps); };
template <class T> inline T sqr(T a) { return a * a; }
inline double min(double a0, double a1) { return a0 > a1 ? a1 : a0; }
struct Point
{
double x, y;
Point() {}
Point(double _x, double _y): x(_x), y(_y) {}
void in();
double dis(const Point &argu) const;
};
void Point::in() { scanf("%lf%lf", &x, &y); }
double Point::dis(const Point &argu) const { return sqrt((x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y)); }
double dis[110][110];
Point pp[110];
double d, t1, t2;
int main()
{
// freopen("E.in", "r", stdin);
while(~scanf("%lf%lf%lf%lf", &pp[0].x, &pp[0].y, &pp[1].x, &pp[1].y))
{
int n; scanf("%d", &n); n += 2;
memset(dis, 0x3f, sizeof(dis));
for(int i = 2; i < n; i++) pp[i].in();
dis[0][1] = dis[1][0] = pp[0].dis(pp[1]) / 5.0;
for(int i = 2; i < n; i++)
{
double d0 = pp[0].dis(pp[i]), d1 = pp[1].dis(pp[i]);
double r0 = d0 / 5.0, r1 = d1 / 5.0;
double c1 = 2 + fabs(r1 - 10.0);
dis[0][i] = dis[i][0] = r0;
dis[1][i] = dis[i][1] = min(r1, c1);
}
for(int i = 2; i < n; i++) for(int j = 2; j < n; j++)
{
double d = pp[i].dis(pp[j]);
double r = d / 5.0;
double c = 2 + fabs(r - 10.0);
dis[i][j] = dis[j][i] = min(r, c);
}
for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
printf("%lf\n", dis[0][1]);
}
return 0;
}</span>
G - Pesky Mosquitoes
定长圆覆盖。
<span style="font-size:18px;">#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define LL long long
#define MAXN 110
#define eps 1e-10
const double pi = acos(-1.0);
inline double sig(double x) { return (x > eps) - (x < -eps); };
template <class T> inline T sqr(T a) { return a * a; }
struct Point
{
double x, y;
Point() {}
Point(double _x, double _y): x(_x), y(_y) {}
void in();
void out() const;
double len() const;
double len2() const;
double dis(const Point &argu) const;
double dis2(const Point &argu) const;
bool operator <(const Point &argu) const;
Point operator -(const Point &argu) const;
double operator ^(const Point &argu) const;
double operator *(const Point &argu) const;
};
struct Segment
{
Point a, b;
Segment() {}
Segment(Point _a, Point _b): a(_a), b(_b) {}
void in();
Point d() const;
void out() const;
double len() const;
double len2() const;
int sgn(const Segment &argu) const;
bool qrt(const Segment &argu) const;
double dis2(const Point &argu) const;
double dis2(const Segment &argu) const;
};
struct Line
{
Segment l;
Line() {}
Line(Segment _l): l(_l) {}
double dis2(const Point &argu) const;
double dis2(const Segment &argu) const;
};
inline double Cross(const Point &o, const Point &a, const Point &b) { return (a - o) ^ (b - o); }
void Point::in() { scanf("%lf%lf", &x, &y); }
double Point::len() const { return sqrt(len2()); }
double Point::len2() const { return x * x + y * y; }
void Point::out() const{ printf("%.0lf %.0lf\n", x, y); }
double Point::dis(const Point &argu) const { return sqrt(dis2(argu)); }
double Point::operator ^(const Point &argu) const { return x * argu.y - y * argu.x; }
double Point::operator *(const Point &argu) const { return x * argu.x + y * argu.y; }
Point Point::operator -(const Point &argu) const { return Point(x - argu.x, y - argu.y); }
bool Point::operator <(const Point &argu) const { return sig(x - argu.x) == 0 ? y < argu.y : x < argu.x; }
double Point::dis2(const Point &argu) const { return (x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y); }
void Segment::in() { a.in(), b.in(); }
Point Segment::d() const { return b - a; }
double Segment::len2() const { return d().len2(); }
double Segment::len() const { return sqrt(len2()); }
void Segment::out() const { a.out(), b.out(); }
double Segment::dis2(const Segment &argu) const
{
if(~sgn(argu)) return 0;
return min(min(dis2(argu.a), dis2(argu.b)), min(argu.dis2(a), argu.dis2(b)));
}
double Segment::dis2(const Point &argu) const
{
Point pa = argu - a, pb = argu - b;
if(sig(d() * pa) <= 0) return pa.len2(); if(sig(d() * pb) >= 0) return pb.len2();
Line l = Line((*this)); return l.dis2(argu);
}
int Segment::sgn(const Segment &argu) const
{
if(!qrt(argu)) return -1;
return sig(Cross(a, b, argu.a)) * sig(Cross(a, b, argu.b)) <= 0 &&
sig(Cross(argu.a, argu.b, a)) * sig(Cross(argu.a, argu.b, b)) <= 0 ? 1 : -1;
}
//快速排斥实验
bool Segment::qrt(const Segment &argu) const
{
return min(a.x, b.x) <= max(argu.a.x, argu.b.x) && min(a.y, b.y) <= max(argu.a.y, argu.b.y) &&
min(argu.a.x, argu.b.x) <= max(a.x, b.x) && min(argu.a.y, argu.b.y) <= max(a.y, b.y);
}
double Line::dis2(const Point &argu) const { return sqr(fabs(l.d() ^ (argu - l.a))) / l.len2(); }
double Line::dis2(const Segment &argu) const
{
Point v1 = argu.a - l.a, v2 = argu.b - l.b; double d1 = l.d() ^ v1, d2 = l.d() ^ v2;
return sig(d1) != sig(d2) ? 0 : sqr(min(fabs(d1), fabs(d2))) / l.len2();
}
struct Arc
{
double ang;
int in;
bool operator <(const Arc &argu) const
{
return sig(ang - argu.ang) ? (ang < argu.ang) : (in > argu.in);
}
}arc[MAXN];
int n;
double r;
Point p[MAXN];
int max(int a, int b) { return a > b ? a : b; }
int MAX_CirCle_Cover(double r)
{
int ret = 0;
for(int i = 0; i < n; i++)
{
int cnt = 0;
for(int j = 0; j < n; j++)
{
if(i == j) continue;
double d = p[i].dis(p[j]);
if(sig(d - 2.0 * r) > 0) continue;
double theta = atan2(p[i].y - p[j].y, p[i].x - p[j].x);
if(theta < 0) theta += 2 * pi;
double phi = acos(d / (2.0 * r));
arc[cnt].ang = theta - phi + 2 * pi; arc[cnt++].in = 1;
arc[cnt].ang = theta + phi + 2 * pi; arc[cnt++].in = 0;
}
sort(arc, arc + cnt);
int tmp = 0;
for(int i = 0; i < cnt; i++)
{
if(arc[i].in) tmp++;
else tmp--;
ret = max(ret, tmp);
}
}
return ret + 1;
}
int work()
{
scanf("%d%lf", &n, &r);
r /= 2.0;
if(sig(r) == 0 || n == 0) return 0;
for(int i = 0; i < n; i++) p[i].in();
return MAX_CirCle_Cover(r);
}
int main()
{
// freopen("G.in", "r", stdin);
int c; scanf("%d", &c);
while(c--)
{
printf("%d\n", work());
}
return 0;
}</span>
K - Yikes ? Bikes!（未完成）
一个胖子要过马路，路上正有一队单车车队经过。
胖子和车队各自的速度恒定。
胖子可以看做一个直径为1m的圆，每个单车可以看做一条长为2m的线段，每个单车之间的间距也是2m。
给出两者速度、给出t=0时，领队的前轮距离胖子所在垂直线的距离、胖子出发的时间；问胖子会抢在第一辆车前过去，还是撞上一辆车，还是在第几辆车后安全通过。
最多只有10辆车。
把胖子的速度转移给单车，这样单车的前段点和后端点的运动路径就是两条向下右斜的平行线。求胖子代表的圆和这些平行的相对位置即可。
胖子的坐标是(0, -0.5)！！！！
然后偷懒，有个很重要的判断没写，居然也过了。。
圆如果在平行线影响范围内，但是是在自行车所代表的的线段的上面（线段也在往下走），那么不能算相撞。
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 10010
#define eps 1e-18
//const double pi = acos(-1.0);
inline double sig(double x) { return (x > eps) - (x < -eps); };
template <class T> inline T sqr(T a) { return a * a; }
struct Point
{
double x, y;
Point() {}
Point(double _x, double _y): x(_x), y(_y) {}
void in();
void out() const;
double len() const;
double len2() const;
double dis(const Point &argu) const;
double dis2(const Point &argu) const;
bool operator <(const Point &argu) const;
Point operator -(const Point &argu) const;
double operator ^(const Point &argu) const;
double operator *(const Point &argu) const;
};
struct Segment
{
Point a, b;
Segment() {}
Segment(Point _a, Point _b): a(_a), b(_b) {}
void in();
Point d() const;
void out() const;
double len() const;
double len2() const;
int sgn(const Segment &argu) const;
bool qrt(const Segment &argu) const;
double dis(const Point &argu) const;
double dis2(const Point &argu) const;
double dis(const Segment &argu) const;
double dis2(const Segment &argu) const;
double operator ^(const Segment &argu) const;
};
struct Line
{
Segment l;
Line() {}
Line(Segment _l): l(_l) {}
Line(Point _a, Point _b): l(Segment(_a, _b)) {}
double dis(const Line &argu) const;
double dis2(const Line &argu) const;
double dis(const Point &argu) const;
double dis2(const Point &argu) const;
double dis(const Segment &argu) const;
double dis2(const Segment &argu) const;
};
inline double Cross(const Point &o, const Point &a, const Point &b) { return (a - o) ^ (b - o); }
void Point::in() { scanf("%lf%lf", &x, &y); }
double Point::len() const { return sqrt(len2()); }
double Point::len2() const { return x * x + y * y; }
void Point::out() const{ printf("%.4lf %.4lf\n", x, y); }
double Point::dis(const Point &argu) const { return sqrt(dis2(argu)); }
double Point::operator ^(const Point &argu) const { return x * argu.y - y * argu.x; }
double Point::operator *(const Point &argu) const { return x * argu.x + y * argu.y; }
Point Point::operator -(const Point &argu) const { return Point(x - argu.x, y - argu.y); }
bool Point::operator <(const Point &argu) const { return sig(x - argu.x) == 0 ? y < argu.y : x < argu.x; }
double Point::dis2(const Point &argu) const { return (x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y); }
void Segment::in() { a.in(), b.in(); }
Point Segment::d() const { return b - a; }
double Segment::len2() const { return d().len2(); }
double Segment::len() const { return sqrt(len2()); }
void Segment::out() const { a.out(), b.out(); }
double Segment::dis2(const Segment &argu) const
{
if(~sgn(argu)) return 0;
return min(min(dis2(argu.a), dis2(argu.b)), min(argu.dis2(a), argu.dis2(b)));
}
double Segment::dis2(const Point &argu) const
{
Point pa = argu - a, pb = argu - b;
if(sig(d() * pa) <= 0) return pa.len2(); if(sig(d() * pb) >= 0) return pb.len2();
Line l = Line((*this)); return l.dis2(argu);
}
int Segment::sgn(const Segment &argu) const
{
if(!qrt(argu)) return -1;
return sig(Cross(a, b, argu.a)) * sig(Cross(a, b, argu.b)) <= 0 &&
sig(Cross(argu.a, argu.b, a)) * sig(Cross(argu.a, argu.b, b)) <= 0 ? 1 : -1;
}
//快速排斥实验
bool Segment::qrt(const Segment &argu) const
{
return min(a.x, b.x) <= max(argu.a.x, argu.b.x) && min(a.y, b.y) <= max(argu.a.y, argu.b.y) &&
min(argu.a.x, argu.b.x) <= max(a.x, b.x) && min(argu.a.y, argu.b.y) <= max(a.y, b.y);
}
double Segment::dis(const Point &argu) const { return sqrt(dis2(argu)); }
double Segment::dis(const Segment &argu) const { return sqrt(dis2(argu)); }
double Line::dis(const Point &argu) const { return sqrt(dis2(argu)); }
double Line::dis2(const Point &argu) const { return sqr(fabs(l.d() ^ (argu - l.a))) / l.len2(); }
double Line::dis(const Segment &argu) const { return sqrt(dis2(argu)); }
double Line::dis2(const Segment &argu) const
{
Point v1 = argu.a - l.a, v2 = argu.b - l.b; double d1 = l.d() ^ v1, d2 = l.d() ^ v2;
return sig(d1) != sig(d2) ? 0 : sqr(min(fabs(d1), fabs(d2))) / l.len2();
}
//Max's speed,
//speed of the cyclists,
//distance in meters between the front of the lead bicycle,
//start time
double m, b, d, t;
int k;
int main()
{
int c; scanf("%d", &c);
Point o(0.0, -0.5);
while(c--)
{
scanf("%lf%lf%lf%lf", &m, &b, &d, &t);
Point a0(t * b - d, 5.0); Point a1(a0.x + b, a0.y - m);
Point b0(a0.x - 2.0, 5.0); Point b1(b0.x + b, b0.y - m);
Line l0(a0, a1), l1(b0, b1);
double lld = l0.dis(l1.l.a);
double d0 = l0.dis(o), d1 = l1.dis(o);
for(int i = 1; i <= 10; i++)
{
if(Cross(a0, o, a1) < 0 && sig(d0 - 0.5) > 0)
{
if(i == 1) puts("Max beats the first bicycle");
else printf("Max crosses safely after bicycle %d\n", i - 1);
break;
}
if(sig(lld - d0 - d1) == 0 || sig(d0 - 0.5) <= 0 || sig(d1 - 0.5) <= 0)
{
printf("Collision with bicycle %d\n", i);
break;
}
if(i == 10)
{
puts("Max crosses safely after bicycle 10");
break;
}
a0.x -= 4.0, a1.x -= 4.0;
l0 = Line(a0, a1), d0 = l0.dis(o);
b0.x -= 4.0, b1.x -= 4.0;
l1 = Line(b0, b1); d1 = l1.dis(o);
}
}
return 0;
}