PKU | |
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 | |
やるだけ
#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; }