Lollypop @ SJTU

             这是新的开始。

好一个圆的面积交啊!

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

const double EPS = 1e-10, PI = acos(-1.);
double Jx, Jy, Rx, Ry, Vj1, Vj2, Vr, Tx, Ty, Tr;

void init()
{
    scanf("%lf%lf%lf%lf", &Rx, &Ry, &Jx, &Jy);
    scanf("%lf%lf%lf", &Tx, &Ty, &Tr);
    scanf("%lf%lf%lf", &Vr, &Vj1, &Vj2);
}

inline double sqr(double x)
{
    return x * x;
}

void get_oval(double x1, double y1, double v1, double x2, double y2, double v2, double &X, double &Y, double &R)
{
    double tmp1 = sqr(v1), tmp2 = sqr(v2);
    double a = 1/tmp1 - 1/tmp2;
    double c = - (2 * x1 / tmp1 - 2 * x2 / tmp2) / a;
    double d = - (2 * y1 / tmp1 - 2 * y2 / tmp2) / a;
    double e = ((sqr(x1) + sqr(y1)) / tmp1 - (sqr(x2) + sqr(y2)) / tmp2) / a;
    //cout << a << ' ' << c << ' ' << d << ' ' << e << endl;
    X = - c / 2, Y = - d / 2, R = sqrt(sqr(c) / 4 + sqr(d) / 4 - e);
}

inline double dis(double x1, double y1, double x2, double y2)
{
    return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}

inline double min(double x, double y)
{
    return x < y ? x : y;
}

inline int dcmp(double x)
{
    return x < -EPS ? -1 : x > EPS;
}

inline void fix(double &x)
{
    while (dcmp(x - 2 * PI) >= 0) x -= 2 * PI;
    while (dcmp(x) < 0) x += 2 * PI;
}

double get_area(double x1, double y1, double r1, double x2, double y2, double r2)
{
    double d = dis(x1, y1, x2, y2);
    if (dcmp(d - abs(r1 - r2)) <= 0) return PI * sqr(min(r1, r2));
    if (dcmp(d - r1 - r2) >= 0) return 0;
    double t1 = ((sqr(r1) - sqr(r2)) / d + d) / 2;
    double t2 = (d - (sqr(r1) - sqr(r2)) / d) / 2;
    if (!dcmp(t1 - t2 - d)) t2 *= -1;
    else if (!dcmp(t2 - t1 - d)) t1 *= -1;
   
    double px = (t1 * x2 + t2 * x1) / (t1 + t2);
    double py = (t1 * y2 + t2 * y1) / (t1 + t2);
    double dx = (x2 - x1) / d, dy = (y2 - y1) / d;
    double l = sqrt(sqr(r1) - sqr(t1));
    double px1 = px - l * dy, py1 = py + l * dx;
    double px2 = px + l * dy, py2 = py - l * dx;
   
    double theta1 = atan2(py1 - y1, px1 - x1) - atan2(py2 - y1, px2 - x1);
    double theta2 = atan2(py2 - y2, px2 - x2) - atan2(py1 - y2, px1 - x2);
   
    fix(theta1);
    fix(theta2);
   
    return abs(theta1 * sqr(r1) / 2 + theta2 * sqr(r2) / 2 - d * l);
}

void solve()
{
    double X1, X2, Y1, Y2, R1, R2;
    get_oval(Jx, Jy, Vj1, Rx, Ry, Vr, X1, Y1, R1);
    get_oval(Jx, Jy, Vj2, Rx, Ry, Vr, X2, Y2, R2);
   
    double s1 = get_area(Tx, Ty, Tr, X1, Y1, R1);
    double s2 = get_area(Tx, Ty, Tr, X2, Y2, R2);
    double s3 = PI * sqr(R2) - get_area(X1, Y1, R1, X2, Y2, R2);
    double ans = dcmp(s3) ? (s2 - s1) / s3 : 0;
    printf("%.4lf\n", ans);
}

int main()
{
    int task;
    scanf("%d", &task);
    for (int i = 1; i <= task; ++i)
    {
        printf("Scenario %d: ", i);
        init();
        solve();
    }
}

原来状态可以这样子优化的 ...
ghy:"条件明确, 要敏感..." 要牢记~~~

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1000 + 10;
int t[MAXN], sum[MAXN];
int lower[MAXN], upper[MAXN];
int f[2][MAXN];
int N, L, C;

void init()
{
  scanf("%d%d", &L, &C);
  for (int i = 1; i <= N; ++i) scanf("%d", &t[i]);
  sum[0] = 0;
  for (int i = 1; i <= N; ++i) sum[i] = sum[i - 1] + t[i];
}

int cost(int T)
{
  T = L - T;
  if (!T) return 0;
  if (T <= 10) return -C;
  return (T - 10) * (T - 10);
}

void solve()
{
  int M = 1, T = 0, tmp;
  for (int i = 1; i <= N; ++i)
    if (T + t[i] > L) T = t[i], upper[M++] = i;
    else T += t[i];
  upper[M] = N + 1;

  tmp = M, T = 0;
  for (int i = N; i >= 1; --i)
    if (T + t[i] > L) T = t[i], lower[tmp--] = i + 1;
    else T += t[i];
  lower[1] = 1;

  f[0][0] = 0, lower[0] = 0, upper[0] = 1;
  for (int i = 1, last = 0, now = 1; i <= M; ++i, last = now, now = 1 - now)
    for (int j = lower[i]; j < upper[i]; ++j)
      {
    f[now][j] = 1 << 30;
    for (int k = lower[i - 1]; k < upper[i - 1]; ++k)
      if (sum[j] - sum[k] <= L)
        f[now][j] <?= f[last][k] + cost(sum[j] - sum[k]);
      }
  printf("Minimum number of lectures: %d\nTotal dissatisfaction index: %d\n", M, f[M & 1][N]);


}

int main()
{
  int data = 0;
  while (scanf("%d", &N), N)
    {
      if (data) printf("\n");
      printf("Case %d:\n\n", ++data);
      init();
      solve();
    }
}

好分治 !!! 漂亮 ... 写得有点纠结 ...

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

int w[10][5], h[10][5];
int W, H;

void update(int dep, int i, int j)
{
  w[dep + 1][i] = w[dep][j];
  h[dep + 1][i] = h[dep][j];
}

bool resize(int ww, int hh, int W, int H)
{
  return !(ww * H - hh * W);
}

bool dfs(int dep, int W, int H, int L)
{
  if (L == 1) return resize(w[dep][0], h[dep][0], W, H);

  for (int i = 1, t; i < H; ++i)
    {
      for (int j = 0; j < L; ++j)
    {
      update(dep, 0, j);
      if (dfs(dep + 1, W, i, 1))
        {
          t = 0;
          for (int k = 0; k < L; ++k)
        if (j != k)  update(dep, t++, k);
          if (dfs(dep + 1, W, H - i, L - 1)) return 1;
        }
    }

      if (L == 4)
    for (int j = 0; j < L; ++j)
      for (int k = j + 1; k < L; ++k)
        {
          update(dep, 0, j), update(dep, 1, k);
          if (!dfs(dep + 1, W, i, 2)) continue;
          t = 0;
          for (int l = 0; l < L; ++l)
        if (l != j && l != k) update(dep, t++, l);
          if (dfs(dep + 1, W, H - i, L - 2)) return 1;
        }
    }

  for (int i = 1, t; i < W; ++i)
    {
      for (int j = 0; j < L; ++j)
    {
      update(dep, 0, j);
      if (dfs(dep + 1, i, H, 1))
        {
          t = 0;
          for (int k = 0; k < L; ++k)
        if (j != k)  update(dep, t++, k);
          if (dfs(dep + 1, W - i, H, L - 1)) return 1;
        }
    }

      if (L == 4)
    for (int j = 0; j < L; ++j)
      for (int k = j + 1; k < L; ++k)
        {
          update(dep, 0, j), update(dep, 1, k);
          if (!dfs(dep + 1, i, H, 2)) continue;
          t = 0;
          for (int l = 0; l < L; ++l)
        if (l != j && l != k) update(dep, t++, l);
          if (dfs(dep + 1, W - i, H, L - 2)) return 1;
        }
    }
  return 0;
}

int main()
{
  int data = 0;
  while (scanf("%d%d", &W, &H), W || H)
    {
      for (int i = 0; i < 4; ++i) scanf("%d%d", &w[0][i], &h[0][i]);
      if (dfs(0, W, H, 4)) printf("Set %d: Yes\n", ++data);
      else printf("Set %d: No\n", ++data);
    }
}

查的好艰辛, 过了 ... 高兴 ~~~

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

const int MAXN = 1010, MAXT = 110, MAXL = 1000100, infinite = 1 << 30;

struct Tnode{
  bool mk;
  int x, y, dp;
} sta[MAXL];
int N, M, L, early, S, T;
string cityName[MAXN];
int l[MAXN], prev[MAXL];
int c[MAXN][MAXT], t[MAXN][MAXT], num[MAXN][MAXT];
map<string, int> hash;

void init()
{
  string st;
  hash.clear();
  for (int i = 0; i < N; ++i)
    cin >> cityName[i], hash[cityName[i]] = i;

  memset(l, 0, sizeof(l));
  cin >> L;
  for (int i = 0; i < L; ++i)
    {
      cin >> l[i];
      for (int j = 0; j < l[i]; ++j)
    {
      cin >> t[i][j] >> st;
      c[i][j] = hash[st];           
    }
    }

  cin >> early;
  cin >> st, S = hash[st];
  cin >> st, T = hash[st];
}

bool cmp(const Tnode & a, const Tnode & b)
{
  if (t[a.x][a.y] != t[b.x][b.y]) return t[a.x][a.y] < t[b.x][b.y];
  if (!a.y || !b.y) return a.y;
  return t[a.x][a.y - 1] < t[b.x][b.y - 1];
}

string space(int x)
{
  if (x >= 1000) return "";
  if (x >= 100) return "0";
  if (x >= 10) return "00";
  else return "000";
}

void prepare()
{
  M = 0;
  for (int i = 0; i < L; ++i)
    for (int j = 0; j < l[i]; ++j)
      sta[M].x = i, sta[M++].y = j;

  sort(sta, sta + M, cmp);
  for (int i = 0; i < M; ++i)
    num[sta[i].x][sta[i].y] = i;

  for (int i = 0; i < M; ++i)
    if (c[sta[i].x][sta[i].y] == S && t[sta[i].x][sta[i].y] >= early)
      sta[i].mk = 1, sta[i].dp = t[sta[i].x][sta[i].y];
    else sta[i].mk = 0, sta[i].dp = 0;
}

void find_prev()
{
  hash.clear();
  memset(prev, -1, sizeof(prev));
  for (int i = 0; i < M; ++i)
    {
      int city = c[sta[i].x][sta[i].y];
      if (hash.count(cityName[city])) prev[i] = hash[cityName[city]];
      hash[cityName[city]] = i;
    }
}

void solve()
{
  prepare();
  find_prev();

  for (int i = 0, j; i < M; ++i)
    {
      if (c[sta[i].x][sta[i].y] == S) continue;
      if (prev[i] >= 0 && sta[prev[i]].mk)
    sta[i].mk = 1, sta[i].dp = sta[prev[i]].dp;
      if (sta[i].y > 0)
    {
      j = num[sta[i].x][sta[i].y - 1];
      if (sta[j].mk)
        sta[i].mk = 1, sta[i].dp >?= sta[j].dp;
    }
    }

  int dep = 0, arr = infinite;
  for (int i = 0; i < M; ++i)
    if (c[sta[i].x][sta[i].y] == T && sta[i].mk)
      {
      if (t[sta[i].x][sta[i].y] < arr)
    arr = t[sta[i].x][sta[i].y], dep = sta[i].dp;
      else if (t[sta[i].x][sta[i].y] == arr)
    dep >?= sta[i].dp;
      }

  if (arr == infinite) cout << "No connection" << endl;
  else cout << "Departure " << space(dep) << dep << ' ' << cityName[S] << endl << "Arrival   " << space(arr) << arr << ' ' << cityName[T] << endl;
}

int main()
{
  int data = 0;
  while (cin >> N && N)
    {
      if (data++) printf("\n");
      cout << "Scenario #" << data << endl;
      init();
      solve();
    }
}

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

using namespace std;

const int dx[4] = {0,1,-1,0};
const int dy[4] = {1,0,0,-1};
const char dir[5] = "NEWS";
const int nx= 12000;

struct nodep
{
  int x , y;
} p[nx];

char s[nx];
int L , flag , len;

bool inside(int x , int x1 , int x2)
{
  return (x - x1) * (x - x2) <= 0;
}

void ho_ho(nodep p1 , nodep p2 , nodep p3 , nodep p4 , nodep &dp)
{
  if (inside(p1.y , p3.y , p4.y) || inside(p2.y , p3.y , p4.y) || inside(p3.y , p1.y , p2.y) || inside(p4.y , p1.y , p2.y))
    dp = p4 , flag = 1;
}

void v_v(nodep p1 , nodep p2 , nodep p3 , nodep p4 , nodep &dp)
{
  if (inside(p1.x , p3.x , p4.x) || inside(p2.x , p3.x , p4.x) || inside(p3.x , p1.x , p2.x) || inside(p4.x , p1.x , p2.x))
    dp = p4 , flag = 1;
}

void ho_v(nodep p1 , nodep p2 , nodep p3 , nodep p4 , nodep &dp)
{
  if (inside(p1.x , p3.x , p4.x) && inside(p3.y , p1.y , p2.y))
    dp.x = p1.x , dp.y = p3.y , flag = 1;
}

int inter(nodep p1 , nodep p2 , nodep &tp)
{
  flag = 0;
  for (int i = 0 ; i < len - 1 ; ++i)
    {
      if (p1.x == p2.x && p[i].x == p[i + 1].x)
 if (p1.x == p[i].x) ho_ho(p[i] , p[i + 1] , p1 , p2 , tp);
 else continue;
      else if (p1.y == p2.y && p[i].y == p[i + 1].y)
 if (p1.y == p[i].y) v_v(p[i] , p[i + 1] , p1 , p2 , tp);
 else continue;
      else if (p1.x == p2.x) ho_v(p1 , p2 , p[i] , p[i + 1] , tp);
      else if (p[i].x == p[i + 1].x) ho_v(p[i] , p[i + 1] , p1 , p2 , tp);
      if (flag) return i + 1;
      //      if (flag && (i != len - 2 || tp.x != p[len - 1].x || tp.y != p[len - 1].y)) return i + 1;
    }
  return -1;
 }

int main()
{
  nodep tp , dp;
  int tot , ddx , ddy , u;

  scanf("%d" , &tot);
  while (tot--)
    {
      scanf("%s" , s);
      L = strlen(s);
      p[0].x = 0 , p[0].y = 0;
      len = 1;
      for (int i = 0 ; i < L ; i += 2)
 {
   for (int j = 0 ; j < 4 ; ++j)
     if (dir[j] == s[i])
       ddx = dx[j] , ddy = dy[j];
   tp.x = p[len - 1].x + ddx * (s[i + 1] - '0');
   tp.y = p[len - 1].y + ddy * (s[i + 1] - '0');
   u = inter(p[len - 1] , tp , dp);
   /*   cout <<i << endl;
   for (int j = 0 ; j < len ; ++j)
     cout << p[j].x << ' ' << p[j].y << endl;
     cout << "------------------------\n";*/
   if (u >= 0)
     {
       len = u;
       if (dp.x != p[len -1].x || dp.y != p[len - 1].y) p[len++] = dp;
     }
   if (tp.x != p[len -1].x || tp.y != p[len - 1].y) p[len++] = tp;
   //   if (dp.x != tp.x || dp.y != tp.y) p[len++] = tp;
 }
      int cnt = 0;
      for (int i = 1 ; i < len ; ++i)
 cnt += abs(p[i].x - p[i - 1].x) + abs(p[i].y - p[i - 1].y);
      printf("%d %d\n" , len - 1 , cnt);
    }
}