Wrong Answer -- japlj

PKU 2540 -- Hotter Colder

PKU | 01:46 |

IOI CanadaはWaterloo大学で行われたが、そのときの Hotter Colder という問題はとてもよい難問だった。

一方 Waterloo local contest 2001.1.17 で出題された Hotter Colder は切るだけだった。

#include<cstdio>
#include<complex>
#include<vector>
#include<algorithm>

using namespace std;

const double EPS=1e-9;

typedef complex<double> pt;
typedef vector<pt> poly;
struct line : vector<pt> {
  line(pt a, pt b) { push_back(a); push_back(b); }
};

double cross(const pt& a, const pt& b) {
  return imag(conj(a)*b);
}
double dot(const pt& a, const pt& b) {
  return real(conj(a)*b);
}
int ccw(pt a, pt b, pt c) {
  b-=a; c-=a;
  if(cross(b,c)>0) return 1; if(cross(b,c)<0) return -1;
  if(dot(b,c)<0) return 2; if(norm(b)<norm(c)) return -2; return 0;
}
pt crosspoint(const line& l, const line& m) {
  double A=cross(l[1]-l[0],m[1]-m[0]), B=cross(l[1]-l[0],l[1]-m[0]);
  if(abs(A)<EPS && abs(B)<EPS) return m[0];
  return m[0]+B/A*(m[1]-m[0]);
}
double area(const poly& P) {
  double a=0;
  for(int i=0; i<(int)P.size(); ++i)
    a+=cross(P[i], P[(i+1)%P.size()]);
  return a/2;
}
double dislp(const line& l, const pt& p) {
  double t = dot(p-l[0],l[0]-l[1])/norm(l[0]-l[1]);
  return abs(p-(l[0]+t*(l[0]-l[1])));
}
poly convex_cut_(const poly& P, const line& l) {
  poly Q;
  for(int i=0; i<(int)P.size(); ++i) {
    pt A=P[i], B=P[(i+1)%P.size()];
    if(ccw(l[0],l[1],A)!=-1) Q.push_back(A);
    if(ccw(l[0],l[1],A)*ccw(l[0],l[1],B)<0) Q.push_back(crosspoint(line(A,B),l));
  }
  return Q;
}
poly convex_cut(poly P, line l, const pt& p) {
  bool nozero=false;
  for(int i=0; i<(int)P.size(); ++i)
    if(ccw(l[0],l[1],P[i])==ccw(l[0],l[1],p)) nozero=true;
  if(!nozero) return poly();
  poly Q = convex_cut_(P, l);
  for(int i=0; i<(int)Q.size(); ++i)
    if(dislp(l, Q[i])>EPS)
      if(ccw(l[0],l[1],Q[i]) == ccw(l[0],l[1],p)) return Q;
#define revx(p) pt(-p.real(),p.imag());
  for(int i=0; i<(int)P.size(); ++i) P[i]=revx(P[i]);
  l[0]=revx(l[0]); l[1]=revx(l[1]);
  Q = convex_cut_(P, l);
  for(int i=0; i<(int)Q.size(); ++i) Q[i]=revx(Q[i]);
  return Q;
}

int main()
{
  poly r(4);
  r[0]=pt(0,0); r[1]=pt(10,0); r[2]=pt(10,10); r[3]=pt(0,10);
  double px=0, py=0, x, y;
  char s[16];
  while(~scanf("%lf%lf%s", &x, &y, s)) {
    if(s[0]=='S') r=poly();
    else if(r.size()>0) {
      pt p(px,py), q(x,y), d(-imag(p-q),real(p-q));
      r=convex_cut(r,line((p+q)/2.,(p+q)/2.+d),s[0]=='C'?p:q);
    }
    r.erase(unique(r.begin(), r.end()), r.end());
    printf("%.2f\n", area(r));
    px=x; py=y;
  }
  return 0;
}

PKU 2509 -- Peter's smokes

PKU | 00:34 |

やるだけ

#include<cstdio>

using namespace std;

int main()
{
  int n, k, s;
  while(~scanf("%d%d", &n, &k)&&(s=n)) {
    while(n>=k) s+=n/k, n=n/k+n%k;
    printf("%d\n", s);
  }
  return 0;
}