Lollypop @ SJTU
ACMICPC 2006 Xi'an Hidden Music Score
小猴 ... 发表于 2008-08-07 21:38:28
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 50;
const double pi = acos(-1.), eps = 1e-8 , EPS = 1e-3;
const double num[7] = {0, 0.5, 1, 1.5, 2, 2.5, 3};
struct Tnode{
double x, y;
Tnode() {};
Tnode(double X, double Y) : x(X), y(Y) {}
} a[MAXN], b[MAXN];
char S, T;
int N, task = 0;
double s, sd;
bool cmp(const Tnode & a, const Tnode & b)
{
return a.x < b.x;
}
bool init()
{
scanf("%d %c %c\n", &N, &S, &T);
if (!N) return 0;
for (int i = 0; i < N; ++i)
scanf("%lf%lf", &a[i].x, &a[i].y);
if (S < 'C') S += 7;
if (T < 'C') T += 7;
s = (T - 'C') - (S - 'C');
return 1;
}
int dcmp_ac(double x)
{
return x < -eps ? -1 : x > eps;
}
int dcmp_ab(double x)
{
return x < -EPS ? -1 : x > EPS;
}
int get_int(double x)
{
return x > 0 ? int(x + 0.5) : int(x - 0.5);
}
bool check()
{
sort(b, b + N, cmp);
int times;
sd = (b[N - 1].y - b[0].y) / s;
if (dcmp_ac(sd - 2.5) > 0 || dcmp_ac(sd - 0.5) < 0) return 0;
for (int i = 1; i < N; ++i)
{
if (dcmp_ac((b[i].x - b[i - 1].x) / sd - 10) > 0 || dcmp_ac((b[i].x - b[i - 1].x) / sd - 2) < 0) return 0;
times = get_int((b[i].y - b[0].y) / sd);
if (dcmp_ab((b[i].y - b[0].y) - times * sd)) return 0;
char ch = times + S;
if (ch < 'C' || ch > 'I') return 0;
}
return 1;
}
void whirl(const Tnode & a, double th, Tnode & b)
{
b.x = a.x * cos(th) - a.y * sin(th);
b.y = a.x * sin(th) + a.y * cos(th);
}
void solve()
{
double theta;
for (int temp = -60; temp <= 60; ++temp)
{
theta = pi * temp / 180;
for (int i = 0; i < N; ++i) whirl(a[i], theta, b[i]);
if (check()) return;
}
}
void print()
{
char ch;
Tnode tmp;
printf("Case %d: ", task);
for (int i = 0; i < N; ++i)
{
ch = get_int((b[i].y - b[0].y) / sd) + S;
if (ch > 'G') ch -= 7;
printf("%c", ch);
}
printf("\n");
}
int main()
{
while (init())
{
++task;
solve();
print();
}
}
PKU1438 One-way Traffic
小猴 ... 发表于 2008-08-07 12:09:49
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 20;
int tot, N, M;
int a[MAXN], b[MAXN];
double c[MAXN * MAXN];
void init()
{
for (int i = 0; i < N; ++i) scanf("%d", &a[i]);
for (int j = 0; j < M; ++j) scanf("%d", &b[j]);
tot = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
c[tot++] = 1. * b[j] / a[i];
sort(c, c + tot);
tot = unique(c, c + tot) - c;
}
void solve()
{
double ans = 1;
for (int i = 1; i < tot; ++i) ans >?= c[i] / c[i - 1];
printf("%.2lf\n", ans);
}
int main()
{
while (scanf("%d%d", &N, &M) == 2)
{
init();
solve();
}
}
PKU1444 Parallelepiped walk
小猴 ... 发表于 2008-08-07 12:06:46
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int r;
void turn(int i, int j, int x, int y, int z, int x0, int y0, int L, int W, int H)
{
if (!z) r <?= x * x + y * y;
else
{
if (i >= 0 && i < 2) turn(i + 1, j, x0 + L + z, y, x0 + L - x, x0 + L, y0, H, W, L);
if (j >= 0 && j < 2) turn(i, j + 1, x, y0 + W + z, y0 + W - y, x0, y0 + W, L, H, W);
if (i <= 0 && i > -2) turn(i - 1, j, x0 - z, y, x - x0, x0 - H, y0, H, W, L);
if (j <= 0 && j > -2) turn(i, j - 1, x, y0 - z, y - y0, x0, y0 - H, L, H, W);
}
}
int main()
{
int L, H, W, x1, y1, z1, x2, y2, z2;
while (scanf("%d%d%d", &L, &W, &H) == 3)
{
scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
if (z1 && z1 != H)
if (y1 == 0 || y1 == W) {swap(y1, z1); swap(y2, z2); swap(W, H);}
else {swap(x1, z1); swap(x2, z2); swap(L, H);}
if (z1 == H) z1 = 0, z2 = H - z2;
r = 0x3fffffff;
turn(0, 0, x2 - x1, y2 - y1, z2, -x1, -y1, L, W, H);
printf("%d\n", r);
}
}
PKU1765 November Rain
小猴 ... 发表于 2008-08-07 12:05:27
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 400400, MAXT = 100;;
struct Troof{
int w;
double k;
int num, nex, deg;
int x1, x2, y1, y2;
} r[MAXN];
int nx[MAXN * 2], a[MAXT], q[MAXN], ans[MAXN];
int N, M, tN;
bool cmp(const Troof & a, const Troof & b)
{
return a.x1 < b.x1;
}
bool init()
{
if (scanf("%d", &N) != 1) return 0;
M = 0;
for (int i = 0; i < N; ++i)
{
r[i].num = i; r[i].w = 0; r[i].deg = 0; r[i].nex = -1;
scanf("%d%d%d%d", &r[i].x1, &r[i].y1, &r[i].x2, &r[i].y2);
r[i].k = 1. * (r[i].y2 - r[i].y1) / (r[i].x2 - r[i].x1);
nx[M++] = r[i].x1; nx[M++] = r[i].x2;
}
sort(nx, nx + M);
M = unique(nx, nx + M) - nx;
sort(r, r + N, cmp);
return 1;
}
inline double y(int num, int x)
{
return r[num].y1 + r[num].k * (x - r[num].x1);
}
void ins(const int & now, int & i)
{
int k;
while (r[i].x1 == now && i < N)
{
k = -1;
for (int j = 0; j < tN; ++j)
if (y(a[j], now) < r[i].y1) k = j;
for (int j = tN - 1; j > k; --j) a[j + 1] = a[j];
a[k + 1] = i; ++tN;
++i;
}
}
inline bool lowSide(const int & i, const int & now)
{
return (r[i].x1 == now && r[i].y1 < r[i].y2 || r[i].x2 == now && r[i].y1 > r[i].y2);
}
void check(const int & now)
{
for (int i = 1; i < tN; ++i)
if (lowSide(a[i], now)) r[a[i]].nex = a[i - 1], ++r[a[i - 1]].deg;
}
void del(const int & now)
{
int j = 0;
for (int i = 0; i < tN; ++i)
if (r[a[i]].x2 != now) a[j++] = a[i];
tN = j;
}
void getAnswer()
{
int op = 0, cl = 0, u, v;
for (int i = 0; i < N; ++i) if (!r[i].deg) q[op++] = i;
for (; cl < op; ++cl)
{
u = q[cl], v = r[u].nex;
if (v == -1) continue;
--r[v].deg; r[v].w += r[u].w;
if (!r[v].deg) q[op++] = v;
}
for (int i = 0; i < N; ++i) ans[r[i].num] = r[i].w;
}
void calc()
{
int last = 0, now, tail = 0;
tN = 0;
for (int t = 0; t < M; last = now, ++t)
{
now = nx[t];
if (tN) r[a[tN - 1]].w += now - last;
ins(now, tail);
check(now);
del(now);
}
getAnswer();
}
void print()
{
for (int i = 0; i < N; ++i) printf("%d\n", ans[i]);
}
int main()
{
while (init())
{
calc();
print();
}
}
PKU1774 Fold Paper Strips
Tsuzuki 发表于 2008-07-31 21:16:36
拿什么来拯救你啊。。。。LOLLYPOP
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int nx = 2000;
const double eps = 1e-12;
struct nodeP
{double x , y;} p[nx][3] , pol[nx][10] , save[nx];
struct nodeL
{double a , b , c;};
int n , step , len;
double dir[nx];
bool suc;
bool init()
{
scanf("%d" , &n);
if (!n) return 0;
for (int i = 0; i < n ; ++i)
{
scanf("%lf %lf" , &p[i][0].x, &p[i][1].x);
scanf("%lf" , &dir[i]);
p[i][0].y = 1 , p[i][1].y = 0;
}
pol[0][0].x = 0 , pol[0][0].y = 0;
pol[0][1].x = 0 , pol[0][1].y = 1;
pol[0][2] = p[0][0] , pol[0][3] = p[0][1] , pol[0][4] = pol[0][0];
return 1;
}
void get_line(nodeL &L , const nodeP &p1 , const nodeP &p2)
{
L.a = p1.x - p2.x , L.b = p1.y - p2.y;
L.c = p1.x * p2.y - p1.y * p2.x;
}
void reflect(nodeP &p , const nodeL &L)
{
double t = (L.b * p.x + L.c - L.a * p.y) / (L.a * L.a + L.b * L.b);
p.x -= L.b * t * 2 , p.y += L.a * t * 2;
}
int dcmp(double x)
{
return x < -eps ? -1 : x > eps;
}
double det(const nodeP &p1 , const nodeP &p2 , const nodeP &p3)
{
return (p1.x - p3.x) * (p2.y - p3.y) - (p1.y - p3.y) * (p2.x - p3.x);
}
double dot(const nodeP &p1 , const nodeP &p2 , const nodeP &p3)
{
return (p1.x - p3.x) * (p2.x - p3.x) + (p1.y - p3.y) * (p2.y - p3.y);
}
bool online(const nodeP &p1 , const nodeP &p2 , const nodeP &p3)
{
return !dcmp(det(p2 , p3 , p1)) && dcmp(dot(p2 , p3 , p1)) < 0;
}
bool equal(const nodeP &p1 , const nodeP &p2)
{
return !dcmp(p1.x - p2.x) && !dcmp(p1.y - p2.y);
}
bool inter(const nodeP &p1 , const nodeP &p2 , const nodeP &p3 , const nodeP &p4)
{
return (dcmp(det(p2 , p3 , p1)) * dcmp(det(p2 , p4 , p1)) < 0 && dcmp(det(p3 , p1 , p4)) * dcmp(det(p3 , p2 , p4)) < 0);
}
bool cmp(const nodeP &p1 , const nodeP &p2)
{
return !dcmp(p1.x - p2.x) ? p1.y < p2.y : p1.x < p2.x;
}
bool inside(int k , const nodeP &p)
{
int ret = 0 , d , u , v;
for (int i = 0 ; i < 4 ; ++i)
if (online(p , pol[k][i] , pol[k][i + 1]) || equal(p , pol[k][i]))
return 0;
else {
d = dcmp(det(pol[k][i + 1] , p , pol[k][i]));
u = dcmp(pol[k][i].y - p.y);
v = dcmp(pol[k][i + 1].y - p.y);
if (d > 0 && u < 0 && v >= 0) ++ret;
if (d < 0 && v < 0 && u >= 0) --ret;
}
return ret;
}
void work()
{
nodeL L;
nodeP tmp;
for (int i = 0 ; i < n ; ++i)
{
if (i && !dcmp(dir[i] - dir[i - 1]))
for (int j = 0 ; j < i ; ++j)
{
len = 2 , save[0] = p[i][0] , save[1] = p[i][1];
for (int k = 0 ; k < 4 ; ++k)
if (inter(p[i][0] , p[i][1] , pol[j][k] , pol[j][k + 1]))
{
suc = 0 , step = i + 1;return;
}
else if (online(pol[j][k] , p[i][0] , p[i][1])) save[len++] = pol[j][k];
sort(save , save + len , cmp);
for (int k = 1 ; k < len ; ++k)
if (!equal(save[k - 1] , save[k]))
{
tmp.x = (save[k].x + save[k - 1].x) / 2;
tmp.y = (save[k].y + save[k - 1].y) / 2;
if (inside(j , tmp))
{
suc = 0 , step = i + 1;
return;
}
}
}
get_line(L , p[i][0] , p[i][1]);
for (int j = 0 ; j <= i ; ++j)
for (int k = 0 ; k <= 4 ; ++k)
reflect(pol[j][k] , L);
if (i < n - 1) {
pol[i + 1][0] = p[i][0] , pol[i + 1][1] = p[i][1];
pol[i + 1][2] = p[i + 1][1] , pol[i + 1][3] = p[i + 1][0];
pol[i + 1][4] = pol[i + 1][0];
}
}
suc = 1;
}
int main()
{
while (init())
{
work();
if (suc) printf("YES\n");
else printf("NO %d\n" , step);
}
}
