Chengrui's Blog

Codeforces 707D Persistent Bookcase

发表于 2016-08-21 分类于 Codeforces Disqus：

链接

题意

给出\(n \times m (1 \leq n, m \leq 10^3)\)矩阵，初始全为0。有\(q (1 \leq q \leq 10^5)\)个操作，可以将一个点置0，将一个点置1，将一行的数字翻转，或回到之前某次操作的状态。对于每次操作输出矩阵中1的个数。

思路

对操作建树，然后在树上dfs求解。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
#include <cassert>
using namespace std;

const int maxn = 1005;
const int maxq = 100005;

int n, m, q;
int x[maxq], y[maxq];
int op[maxq], ans[maxq];
bool flag[maxq], rev[maxn];
vector<int> g[maxq];
bitset<maxn> a[maxn], tmp[maxq];

void dfs(int u, int res) {
  tmp[u] = a[x[u]];
  flag[u] = rev[x[u]];
  if (op[u] == 3) {
    rev[x[u]] = !rev[x[u]];
  } else if (op[u] != 0) {
    a[x[u]][y[u]] = flag[u] ? 1 - (op[u] & 1) : (op[u] & 1);
  }
  res -= flag[u] ? m - tmp[u].count() : tmp[u].count();
  res += rev[x[u]] ? m - a[x[u]].count(): a[x[u]].count();
  ans[u] = res;
  for (int v: g[u]) {
    dfs(v, res);
  }
  a[x[u]] = tmp[u];
  rev[x[u]] = flag[u];
}

int main() {
  int pre = 0;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= q; ++i) {
    scanf("%d%d", &op[i], &x[i]);
    if (op[i] < 3) {
      scanf("%d", &y[i]);
    }
    if (op[i] == 4) {
      pre = x[i];
      while (op[pre] == 4) {
        x[i] = x[pre];
        pre = x[pre];
      }
    } else {
      g[pre].push_back(i);
      pre = i;
    }
  }
  dfs(0, 0);
  for (int i = 1; i <= q; ++i) {
    if (op[i] == 4) {
      printf("%d\n", ans[x[i]]);
    } else {
      printf("%d\n", ans[i]);
    }
  }
  return 0;
}

Codeforces 707C Pythagorean Triples

发表于 2016-08-21 分类于 Codeforces Disqus：

链接

传送门

题意

给出\(n(1 \leq n \leq 10^9)\)，输出与\(n\)能够组成直角三角形的两条边的长度，无解输出－1。

思路

\(n \leq 2\)时，无解。
\(n \geq 3\)且为奇数时，满足\({\left( \frac{n^2 - 1}{2} \right)}^2 + n^2 = {\left( \frac{n^2 + 1}{2} \right)}^2\)
\(n \geq 4\)且为偶数时，满足\({\left( \frac{n^2}{4} - 1 \right)}^2 + n^2 = {\left( \frac{n^2}{4} + 1 \right)}^2\)

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int main() {
  int n;
  scanf("%d", &n);
  if (n <= 2) {
    puts("-1");
    return 0;
  }
  LL m = 0, k = 0;
  if (n & 1) {
    m = (LL(n) * n - 1) / 2;
    k = m + 1;
  } else {
    m = LL(n) * n / 4 - 1;
    k = m + 2;
  }
  printf("%I64d %I64d\n", m, k);
  return 0;
}

UVa 438 - The Circumference of the Circle

发表于 2016-08-18 分类于 AOAPC Training Guide ， Chapter 4. Geometry ， Basic Problems Disqus：

链接

传送门

题意

给出三角形三个顶点坐标，求三角形外接圆半径。

思路

套用外心模版。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

struct Point {
  double x, y;
  Point() {}
  Point(double x, double y): x(x), y(y) {}
} A, B, C;

double Length(const Point& a) {
  return sqrt(a.x * a.x + a.y * a.y);
}

int main() {
  while (~scanf("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y)) {
    Point p;
    double a1 = B.x - A.x, b1 = B.y - A.y, c1 = (a1 * a1 + b1 * b1) / 2;
    double a2 = C.x - A.x, b2 = C.y - A.y, c2 = (a2 * a2 + b2 * b2) / 2;
    double d = a1 * b2 - a2 * b1;
    p.x = (c1 * b2 - c2 * b1) / d;
    p.y = (a1 * c2 - a2 * c1) / d;
    double r = Length(p);
    printf("%.2f\n", M_PI * r * 2);
  }
  return 0;
}

UVa 10522 - Height to Area

发表于 2016-08-17 分类于 AOAPC Training Guide ， Chapter 4. Geometry ， Basic Problems Disqus：

链接

传送门

题意

给出三角形的三条高的长度，求三角形的面积。

思路

设三角形的三边为\(a\)、\(b\)、\(c\)，对应的高分别为\(h_a\)、\(h_b\)、\(h_c\)，三角形的面积为\(s\)。

显然

\[a = \frac{2s}{h_a}, \space b = \frac{2s}{h_b}, \space c = \frac{2s}{h_c}\]

又因为

\[s = \sqrt{p \left( p - a \right) \left( p - b \right) \left( p - c \right)}\] \[p = \frac{1}{2} \left(a + b + c\right) = s\left(\frac{1}{h_a} + \frac{1}{h_b} + \frac{1}{h_c} \right)\]

化简得

\[s = \frac{1}{\sqrt{\left( \frac{1}{h_a} + \frac{1}{h_b} + \frac{1}{h_c} \right) \left( -\frac{1}{h_a} + \frac{1}{h_b} + \frac{1}{h_c} \right) \left( \frac{1}{h_a} - \frac{1}{h_b} + \frac{1}{h_c} \right) \left( \frac{1}{h_a} + \frac{1}{h_b} - \frac{1}{h_c} \right)}}\]

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;


int main() {
  int t;
  scanf("%d", &t);
  while (t) {
    double ha, hb, hc;
    scanf("%lf%lf%lf", &ha, &hb, &hc);
    if (ha == 0 || hb == 0 || hc == 0) {
      puts("These are invalid inputs!");
      --t;
    } else {
      double a = 1 / ha, b = 1 / hb, c = 1 / hc;
      double p = a + b + c, pa = -a + b + c, pb = a - b + c, pc = a + b - c;
      double s = p * pa * pb * pc;
      if (s <= 0) {
        puts("These are invalid inputs!");
        --t;
      } else {
        printf("%.3f\n", 1 / sqrt(s));
      }
    }
  }
  return 0;
}

UVa 10439 - Temple of Dune

发表于 2016-08-17 分类于 AOAPC Training Guide ， Chapter 4. Geometry ， Basic Problems Disqus：

链接

传送门

题意

给出三个点，问这三个点最少是正几边形的顶点。

思路

之前组队赛做过，三个点在正多边形的外接圆，三个点的两两关于圆心的夹角是正多边形相邻两点圆心角的倍数，枚举正多边形的边数依次检验即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const double eps = 1e-5;
const double PI2 = acos(-1) * 2;
const int maxn = 5;
const int maxm = 1010;
double ANG[maxm];

struct Point {
  double x, y;
  Point() {}
  Point(double x, double y) : x(x), y(y) {}
} p[maxn];

typedef Point Vector;

Vector operator - (Vector a, Vector b) {
  return Vector(a.x - b.x, a.y - b.y);
}

int dcmp(double x) {
  if (fabs(x) < eps) {
    return 0;
  }
  return x > 0 ? 1 : -1;
}

double Dot(const Vector& A, const Vector& B) {
  return A.x * B.x + A.y * B.y;
}

double Length(const Vector& A) {
  return sqrt(Dot(A, A));
}

double Angle(const Vector& A, const Vector& B) {
  return acos(Dot(A, B) / Length(A) / Length(B));
}

bool check(double a, double mod) {
  a -= floor(a / mod) * mod;
  return dcmp(a) == 0 || dcmp(a - mod) == 0;
}

int main() {
  for (int i = 3; i < maxm; ++i) {
    ANG[i] = PI2 / i;
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    for (int i = 0; i < 3; ++i) {
      scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    double ang1 = 2 * Angle(p[0] - p[2], p[1] - p[2]);
    double ang2 = 2 * Angle(p[1] - p[0], p[2] - p[0]);
    double ang3 = 2 * Angle(p[2] - p[1], p[0] - p[1]);
    int ans = 0;
    for (int i = 3; i < maxm; ++i) {
      if (check(ang1, ANG[i]) && check(ang2, ANG[i]) && check(ang3, ANG[i])) {
        ans = i;
        break;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 10347 - Medians

发表于 2016-08-17 分类于 AOAPC Training Guide ， Chapter 4. Geometry ， Basic Problems Disqus：

链接

传送门

题意

给出三条边作为三角形的中线，求三角形的面积，不合法输出“-1.000”。

思路

三角形的中线可以组成三角形，其面积是原三角形面积的\(\frac{3}{4}\)。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  double a, b, c;
  while (~scanf("%lf%lf%lf", &a, &b, &c)) {
    if (a + b <= c || a + c <= b || b + c <= a) {
      puts("-1.000");
    } else {
      double p = (a + b + c) / 2;
      printf("%.3f\n", sqrt(p * (p - a) * (p - b) * (p - c)) * 4 / 3);
    }
  }
  return 0;
}

UVa 1447 - Malfatti Circles

发表于 2016-08-17 分类于 AOAPC Training Guide ， Chapter 4. Geometry ， Basic Problems Disqus：

链接

传送门

题意

给出三角形的三个顶点坐标，求三个Malfatti Circle的半径。

思路

参考维基百科中对Malfatti Circle的介绍，其半径公式为：

\[r_1 = \frac{r}{2 \left(s - a\right)} \left( s + d - r - e - f \right)\]

式中\(s\)为三角形的周长，\(d\)、\(e\)、\(f\)分别为\(A\)、\(B\)、\(C\)三个顶点到三角形内心的距离。其余两个Malfatti Circle的半径计算与之同理。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point {
  double x, y;
  Point() {}
  Point(double x, double y): x(x), y(y) {}
} A, B, C;

typedef Point Vector;

Vector operator - (const Point& a, const Point& b) {
  return Vector(a.x - b.x, a.y - b.y);
}

double Dot(const Point& a, const Point& b) {
  return a.x * b.x + a.y * b.y;
}

double Cross(const Point& a, const Point& b) {
  return a.x * b.y - a.y * b.x;
}

double Length(const Vector& a) {
  return sqrt(Dot(a, a));
}

int main() {
  while (~scanf("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y) && (A.x || A.y || B.x || B.y || C.x ||C.y)) {
    double a = Length(B - C);
    double b = Length(C - A);
    double c = Length(A - B);
    Point O;
    O.x = (a * A.x + b * B.x + c * C.x) / (a + b + c);
    O.y = (a * A.y + b * B.y + c * C.y) / (a + b + c);
    double s = (a + b + c) / 2, r = fabs(Cross(B - A, C - A)) / (a + b + c);
    double d = Length(A - O), e = Length(B - O), f = Length(C - O);
    double ra = r / 2 / (s - a) * (s + d - r - e - f);
    double rb = r / 2 / (s - b) * (s + e - r - d - f);
    double rc = r / 2 / (s - c) * (s + f - r - d - e);
    printf("%.6f %.6f %.6f\n", ra, rb, rc);
  }
  return 0;
}

UVa 12165 - Triangle Hazard

发表于 2016-08-17 分类于 AOAPC Training Guide ， Chapter 4. Geometry ， Basic Problems Disqus：

链接

传送门

题意

如图，给出\(P\)、\(Q\)、\(R\)三个点的坐标和\(m1:m2\)、\(m3:m4\)、\(m5:m6\)的值。求\(A\)、\(B\)、\(C\)的坐标。

思路

由梅涅劳斯定理可得：

\[\frac{AR}{RP} \cdot \frac{PQ}{QB} \cdot \frac{BD}{DC} = 1\]

即：

\[\frac{AR}{RP} \cdot \frac{PQ}{QB} = \frac{m_5}{m_6}\]

设

\[k_1 = \frac{m_5}{m_6}, \space k_2 = \frac{m_1}{m_2}, \space k_3 = \frac{m_3}{m_4}\]

化简得：

\[\frac{AR}{RP} = k_1 \left( \frac{BP}{PQ} + 1 \right)\]

同理可得，

\[\frac{BP}{PQ} = k_2 \left( \frac{CQ}{QR} + 1 \right), \space \frac{CQ}{QR} = k_3 \left( \frac{AR}{RP} + 1 \right)\]

解得：

\[\frac{AR}{RP} = \frac{k_1k_2k_3 + k_1k_2 + k_1}{1 - k_1k_2k_3}\]

\[\frac{BP}{PQ} = \frac{k_1k_2k_3 + k_2k_3 + k_2}{1 - k_1k_2k_3}\]

\[\frac{CQ}{QR} = \frac{k_1k_2k_3 + k_3k_1 + k_3}{1 - k_1k_2k_3}\]

然后利用向量乘法很容易解决了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point {
  double x, y;
  Point() {}
  Point(double x, double y): x(x), y(y) {}
} P, Q, R, A, B, C;

typedef Point Vector;

Vector operator + (const Point& a, const Point& b) {
  return Point(a.x + b.x, a.y + b.y);
}

Vector operator - (const Point& a, const Point& b) {
  return Point(a.x - b.x, a.y - b.y);
}

Vector operator * (const Point& a, const double& k) {
  return Point(a.x * k, a.y * k);
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    double m1, m2, m3, m4, m5, m6;
    scanf("%lf%lf%lf%lf%lf%lf", &P.x, &P.y, &Q.x, &Q.y, &R.x, &R.y);
    scanf("%lf%lf%lf%lf%lf%lf", &m1, &m2, &m3, &m4, &m5, &m6);
    double k1 = m5 / m6, k2 = m1 / m2, k3 = m3 / m4, k = k1 * k2 * k3;
    A = (R - P) * ((k + k1 * k2 + k1) / (1 - k)) + R;
    B = (P - Q) * ((k + k2 * k3 + k2) / (1 - k)) + P;
    C = (Q - R) * ((k + k3 * k1 + k3) / (1 - k)) + Q;
    printf("%.8f %.8f %.8f %.8f %.8f %.8f\n", A.x, A.y, B.x, B.y, C.x, C.y);
  }
  return 0;
}

UVa 10566 - Crossed Ladders

发表于 2016-08-15 分类于 AOAPC Training Guide ， Chapter 4. Geometry ， Basic Problems Disqus：

链接

传送门

题意

两个梯子放置在交叉靠在墙上，长度分别为\(x\)和\(y\)，交点离地面的高度为\(c\)，求两个墙间的距离。

思路

根据相似关系列方程，二分答案。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const double eps = 1e-8;
double x, y, c;

double cal(double k) {
  return c / sqrt(x * x - k * k) + c / sqrt(y * y - k * k);
}

int main() {
  while (~scanf("%lf%lf%lf", &x, &y, &c)) {
    if (x > y) {
      swap(x, y);
    }
    double L = 0, R = x;
    while (R - L > eps) {
      double M = (L + R) / 2;
      if (cal(M) < 1) {
        L = M;
      } else {
        R = M;
      }
    }
    printf("%.3f\n", (L + R) / 2);
  }
  return 0;
}

UVa 11731 - Ex-circles

发表于 2016-08-15 分类于 AOAPC Training Guide ， Chapter 4. Geometry ， Basic Problems Disqus：

链接

传送门

题意

给出一个三角形和它的三个旁切圆，求指定部分的面积。具体见原题。

思路

利用旁切圆半径公式即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

double Area(double a, double b, double c) {
  double p = (a + b + c) / 2;
  return sqrt(p * (p - a) * (p - b) * (p - c));
}

double Ang(double a, double b, double c) {
  return acos((c * c - a * a - b * b) / (2 * a * b));
}

int main() {
  int a, b, c, t = 0;
  while (~scanf("%d%d%d", &a, &b, &c) && (a || b || c)) {
    double S = Area(a, b, c);
    double ra = 2 * S / (-a + b + c);
    double rb = 2 * S / (a - b + c);
    double rc = 2 * S / (a + b - c);
    double A = Ang(b, c, a);
    double B = Ang(a, c, b);
    double C = Ang(a, b, c);
    double ans1 = S + (a * ra + b * rb + c * rc) / 2;
    double ans2 = A * ra * ra + B * rb * rb + C * rc * rc;
    printf("Case %d: %.2f %.2f\n", ++t, ans1, ans2 / 4);
  }
  return 0;
}