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;
}