#include <math.h>
#include <stdlib.h>
#include <stdio.h>
struct Vec{double x, y, z;Vec(double x_=0,double y_=0,double z_=0){x=x_;y=
y_; z=z_; } Vec operator+(const Vec &b) const { return Vec(x+b.x,y+b.y,
z+b.z); } Vec operator-(const Vec &b) const { return Vec(x-b.x,y-b.y,z-
b.z); } Vec operator*(double b) const { return Vec(x*b,y*b,z*b); } Vec
mult(const Vec &b) const { return Vec(x*b.x,y*b.y,z*b.z); } Vec& norm(){
return *this = *this * (1/sqrt(x*x+y*y+z*z)); } double dot(const Vec &
b) const { return x*b.x+y*b.y+z*b.z; } Vec operator%(Vec&b){return
Vec(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);}};struct Ray { Vec o, d; Ray(
Vec o_, Vec d_) : o(o_), d(d_) {} };enum Refl_t { DIFF, SPEC, REFR };
struct Sphere { double rad; Vec p, e, c; Refl_t refl; Sphere(double
rad_, Vec p_, Vec e_, Vec c_, Refl_t refl_): rad(rad_), p(p_), e(e_),
c(c_), refl(refl_) {} double intersect(const Ray &r) const { Vec op =
p-r.o; double t, eps=1e-4, b=op.dot(r.d), det=b*b-op.dot(op)+rad*rad;
if (det<0) return 0; else det=sqrt(det); return (t=b-det)>eps ? t : ((
t=b+det)>eps ? t : 0); }};Sphere spheres[] = { Sphere(1e5, Vec( 1e5+1,40.8,81.6),
Vec(),Vec(.75,.25,.25),DIFF), Sphere(1e5, Vec(-1e5+99,40.8,81.6),Vec(),
Vec(.25,.25,.75),DIFF), Sphere(1e5, Vec(50,40.8, 1e5), Vec(),Vec(.75,.75,.75),
DIFF), Sphere(1e5, Vec(50,40.8,-1e5+170), Vec(),Vec(), DIFF), Sphere(1
e5, Vec(50, 1e5, 81.6), Vec(),Vec(.75,.75,.75),DIFF), Sphere(1e5, Vec(50,-1
e5+81.6,81.6),Vec(),Vec(.75,.75,.75),DIFF), Sphere(16.5,Vec(27,16.5,47),
Vec(),Vec(1,1,1)*.999, SPEC), Sphere(16.5,Vec(73,16.5,78), Vec(),Vec(1,1,1)*.999,
REFR), Sphere(600, Vec(50,681.6-.27,81.6),Vec(12,12,12), Vec(), DIFF) };
inline double clamp(double x){ return x<0 ? 0 : x>1 ? 1 : x; }inline
int toInt(double x){ return int(pow(clamp(x),1/2.2)*255+.5); }inline
bool intersect(const Ray &r, double &t, int &id){ double n=sizeof(
spheres)/sizeof(Sphere), d, inf=t=1e20; for(int i=int(n);i--;) if((d=
spheres[i].intersect(r))&&d<t){t=d;id=i;} return t<inf;}Vec radiance(
const Ray &r, int depth, unsigned short *Xi){ double t; int id=0; if (!
intersect(r, t, id)) return Vec(); const Sphere &obj = spheres[id];
Vec x=r.o+r.d*t, n=(x-obj.p).norm(), nl=n.dot(r.d)<0?n:n*-1, f=obj.c;
double p = f.x>f.y && f.x>f.z ? f.x : f.y>f.z ? f.y : f.z; if (++
depth>5) if (erand48(Xi)<p) f=f*(1/p); else return obj.e; if (obj.
refl == DIFF){ double r1=2*M_PI*erand48(Xi), r2=erand48(Xi), r2s=sqrt(
r2); Vec w=nl, u=((fabs(w.x)>.1?Vec(0,1):Vec(1))%w).norm(), v=w%u; Vec
d = (u*cos(r1)*r2s + v*sin(r1)*r2s + w*sqrt(1-r2)).norm(); return obj.
e + f.mult(radiance(Ray(x,d),depth,Xi)); } else if (obj.refl == SPEC)
return obj.e + f.mult(radiance(Ray(x,r.d-n*2*n.dot(r.d)),depth,Xi));
Ray reflRay(x, r.d-n*2*n.dot(r.d)); bool into = n.dot(nl)>0; double
nc=1, nt=1.5, nnt=into?/nt:/nc, ddn=r.d.dot(nl), cos2t; if ((cos2t=1-
nnt*nnt*(1-ddn*ddn))<0) return obj.e + f.mult(radiance(reflRay,depth,
Xi)); Vec tdir = (r.d*nnt - n*((into?1:-1)*(ddn*nnt+sqrt(cos2t)))).
norm(); double a=nt-nc, b=nt+nc, R0=a*/(b*b), c = 1-(into?-ddn:tdir.
dot(n)); double Re=R0+(1-R0)*c*c*c*c*c,Tr=1-Re,P=.25+.5*Re,RP=/P,TP=/(1-
P); return obj.e + f.mult(depth>2 ? (erand48(Xi)<P ? radiance(reflRay,
depth,Xi)*RP:radiance(Ray(x,tdir),depth,Xi)*TP) : radiance(reflRay,
depth,Xi)*Re+radiance(Ray(x,tdir),depth,Xi)*Tr);}int main(int argc,
char *argv[]){ int w=1024, h=768, samps = argc==2 ? atoi(argv[1])/4 : 1;
Ray cam(Vec(50,52,295.6), Vec(0,-0.042612,-1).norm()); Vec cx=Vec(w*.5135/
h), cy=(cx%cam.d).norm()*.5135, r, *c=new Vec[w*h];
#pragma omp parallel for schedule(dynamic, 1) private(r)
for (int y=0; y<h; y++){fprintf(stderr,"\rRendering(%d spp) %5.2f%%",
samps*4,100.*y/(h-1));for (unsigned short x=0, Xi[3]={0,0,y*y*y}; x<w;
x++)for (int sy=0,i=(h-y-1)*w+x; sy<2; sy++) for (int sx=0; sx<2; sx++,
r=Vec()){for(int s=0; s<samps; s++){double r1=2*erand48(Xi),dx=r1<1?sqrt
(r1)-1:1-sqrt(2-r1); double r2=2*erand48(Xi), dy=r2<1 ? sqrt(r2)-1: 1-sqrt
(2-r2);Vec d=cx*(((sx+.5+dx)/2+x)/w-.5)+cy*(((sy+.5+dy)/2+y)/
h-.5)+cam.d;r=r+radiance(Ray(cam.o+d*140,d.norm()),0,Xi)*(1./
samps);}c[i]=c[i]+Vec(clamp(r.x),clamp(r.y),clamp(r.z))*.25;}}
FILE *f=fopen("image.ppm","w");fprintf(f,"P3\n%d %d\n%d\n",w,h,255);
for(int i=0;i<w*h;i++)fprintf(f,"%d %d %d ",toInt(c[i].x),toInt(
c[i].y),toInt(c[i].z));}
I2luY2x1ZGUgPG1hdGguaD4gCiNpbmNsdWRlIDxzdGRsaWIuaD4gCiNpbmNsdWRlIDxzdGRpby5oPiAKc3RydWN0IFZlY3tkb3VibGUgeCwgeSwgejtWZWMoZG91YmxlIHhfPTAsZG91YmxlIHlfPTAsZG91YmxlIHpfPTApe3g9eF87eT0KeV87IHo9el87IH0gVmVjIG9wZXJhdG9yKyhjb25zdCBWZWMgJmIpIGNvbnN0IHsgcmV0dXJuIFZlYyh4K2IueCx5K2IueSwKeitiLnopOyB9IFZlYyBvcGVyYXRvci0oY29uc3QgVmVjICZiKSBjb25zdCB7IHJldHVybiBWZWMoeC1iLngseS1iLnksei0KYi56KTsgfSBWZWMgb3BlcmF0b3IqKGRvdWJsZSBiKSBjb25zdCB7IHJldHVybiBWZWMoeCpiLHkqYix6KmIpOyB9IFZlYyAKbXVsdChjb25zdCBWZWMgJmIpIGNvbnN0IHsgcmV0dXJuIFZlYyh4KmIueCx5KmIueSx6KmIueik7IH0gVmVjJiBub3JtKCl7IApyZXR1cm4gKnRoaXMgPSAqdGhpcyAqICgxL3NxcnQoeCp4K3kqeSt6KnopKTsgfSBkb3VibGUgZG90KGNvbnN0IFZlYyAmCmIpIGNvbnN0IHsgcmV0dXJuIHgqYi54K3kqYi55K3oqYi56OyB9ICBWZWMgb3BlcmF0b3IlKFZlYyZiKXtyZXR1cm4gClZlYyh5KmIuei16KmIueSx6KmIueC14KmIueix4KmIueS15KmIueCk7fX07c3RydWN0IFJheSB7IFZlYyBvLCBkOyBSYXkoClZlYyBvXywgVmVjIGRfKSA6IG8ob18pLCBkKGRfKSB7fSB9O2VudW0gUmVmbF90IHsgRElGRiwgU1BFQywgUkVGUiB9OyAKc3RydWN0IFNwaGVyZSB7IGRvdWJsZSByYWQ7ICBWZWMgcCwgZSwgYzsgIFJlZmxfdCByZWZsOyAgU3BoZXJlKGRvdWJsZSAKcmFkXywgVmVjIHBfLCBWZWMgZV8sIFZlYyBjXywgUmVmbF90IHJlZmxfKTogcmFkKHJhZF8pLCBwKHBfKSwgZShlXyksIApjKGNfKSwgcmVmbChyZWZsXykge30gZG91YmxlIGludGVyc2VjdChjb25zdCBSYXkgJnIpIGNvbnN0IHsgIFZlYyBvcCA9IApwLXIubzsgIGRvdWJsZSB0LCBlcHM9MWUtNCwgYj1vcC5kb3Qoci5kKSwgZGV0PWIqYi1vcC5kb3Qob3ApK3JhZCpyYWQ7IAppZiAoZGV0PDApIHJldHVybiAwOyBlbHNlIGRldD1zcXJ0KGRldCk7IHJldHVybiAodD1iLWRldCk+ZXBzID8gdCA6ICgoCnQ9YitkZXQpPmVwcyA/IHQgOiAwKTsgfX07U3BoZXJlIHNwaGVyZXNbXSA9IHsgU3BoZXJlKDFlNSwgVmVjKCAxZTUrMSw0MC44LDgxLjYpLCAKVmVjKCksVmVjKC43NSwuMjUsLjI1KSxESUZGKSwgU3BoZXJlKDFlNSwgVmVjKC0xZTUrOTksNDAuOCw4MS42KSxWZWMoKSwKVmVjKC4yNSwuMjUsLjc1KSxESUZGKSwgU3BoZXJlKDFlNSwgVmVjKDUwLDQwLjgsIDFlNSksIFZlYygpLFZlYyguNzUsLjc1LC43NSksCkRJRkYpLCBTcGhlcmUoMWU1LCBWZWMoNTAsNDAuOCwtMWU1KzE3MCksIFZlYygpLFZlYygpLCBESUZGKSwgU3BoZXJlKDEKZTUsIFZlYyg1MCwgMWU1LCA4MS42KSwgVmVjKCksVmVjKC43NSwuNzUsLjc1KSxESUZGKSwgU3BoZXJlKDFlNSwgVmVjKDUwLC0xCmU1KzgxLjYsODEuNiksVmVjKCksVmVjKC43NSwuNzUsLjc1KSxESUZGKSwgU3BoZXJlKDE2LjUsVmVjKDI3LDE2LjUsNDcpLCAKVmVjKCksVmVjKDEsMSwxKSouOTk5LCBTUEVDKSwgU3BoZXJlKDE2LjUsVmVjKDczLDE2LjUsNzgpLCBWZWMoKSxWZWMoMSwxLDEpKi45OTksIApSRUZSKSwgU3BoZXJlKDYwMCwgVmVjKDUwLDY4MS42LS4yNyw4MS42KSxWZWMoMTIsMTIsMTIpLCBWZWMoKSwgRElGRikgfTsKaW5saW5lIGRvdWJsZSBjbGFtcChkb3VibGUgeCl7IHJldHVybiB4PDAgPyAwIDogeD4xID8gMSA6IHg7IH1pbmxpbmUgCmludCB0b0ludChkb3VibGUgeCl7IHJldHVybiBpbnQocG93KGNsYW1wKHgpLDEvMi4yKSoyNTUrLjUpOyB9aW5saW5lIApib29sIGludGVyc2VjdChjb25zdCBSYXkgJnIsIGRvdWJsZSAmdCwgaW50ICZpZCl7IGRvdWJsZSBuPXNpemVvZigKc3BoZXJlcykvc2l6ZW9mKFNwaGVyZSksIGQsIGluZj10PTFlMjA7IGZvcihpbnQgaT1pbnQobik7aS0tOykgaWYoKGQ9CnNwaGVyZXNbaV0uaW50ZXJzZWN0KHIpKSYmZDx0KXt0PWQ7aWQ9aTt9IHJldHVybiB0PGluZjt9VmVjIHJhZGlhbmNlKApjb25zdCBSYXkgJnIsIGludCBkZXB0aCwgdW5zaWduZWQgc2hvcnQgKlhpKXsgZG91YmxlIHQ7ICBpbnQgaWQ9MDsgIGlmICghCmludGVyc2VjdChyLCB0LCBpZCkpIHJldHVybiBWZWMoKTsgIGNvbnN0IFNwaGVyZSAmb2JqID0gc3BoZXJlc1tpZF07ICAKVmVjIHg9ci5vK3IuZCp0LCBuPSh4LW9iai5wKS5ub3JtKCksIG5sPW4uZG90KHIuZCk8MD9uOm4qLTEsIGY9b2JqLmM7IApkb3VibGUgcCA9IGYueD5mLnkgJiYgZi54PmYueiA/IGYueCA6IGYueT5mLnogPyBmLnkgOiBmLno7ICBpZiAoKysKZGVwdGg+NSkgaWYgKGVyYW5kNDgoWGkpPHApIGY9ZiooMS9wKTsgZWxzZSByZXR1cm4gb2JqLmU7ICBpZiAob2JqLgpyZWZsID09IERJRkYpeyAgZG91YmxlIHIxPTIqTV9QSSplcmFuZDQ4KFhpKSwgcjI9ZXJhbmQ0OChYaSksIHIycz1zcXJ0KApyMik7IFZlYyB3PW5sLCB1PSgoZmFicyh3LngpPi4xP1ZlYygwLDEpOlZlYygxKSkldykubm9ybSgpLCB2PXcldTsgVmVjIApkID0gKHUqY29zKHIxKSpyMnMgKyB2KnNpbihyMSkqcjJzICsgdypzcXJ0KDEtcjIpKS5ub3JtKCk7IHJldHVybiBvYmouCmUgKyBmLm11bHQocmFkaWFuY2UoUmF5KHgsZCksZGVwdGgsWGkpKTsgfSBlbHNlIGlmIChvYmoucmVmbCA9PSBTUEVDKSAgCnJldHVybiBvYmouZSArIGYubXVsdChyYWRpYW5jZShSYXkoeCxyLmQtbioyKm4uZG90KHIuZCkpLGRlcHRoLFhpKSk7IApSYXkgcmVmbFJheSh4LCByLmQtbioyKm4uZG90KHIuZCkpOyAgYm9vbCBpbnRvID0gbi5kb3QobmwpPjA7ICBkb3VibGUgCm5jPTEsIG50PTEuNSwgbm50PWludG8/L250Oi9uYywgZGRuPXIuZC5kb3QobmwpLCBjb3MydDsgaWYgKChjb3MydD0xLQpubnQqbm50KigxLWRkbipkZG4pKTwwKSAgcmV0dXJuIG9iai5lICsgZi5tdWx0KHJhZGlhbmNlKHJlZmxSYXksZGVwdGgsClhpKSk7IFZlYyB0ZGlyID0gKHIuZCpubnQgLSBuKigoaW50bz8xOi0xKSooZGRuKm5udCtzcXJ0KGNvczJ0KSkpKS4Kbm9ybSgpOyBkb3VibGUgYT1udC1uYywgYj1udCtuYywgUjA9YSovKGIqYiksIGMgPSAxLShpbnRvPy1kZG46dGRpci4KZG90KG4pKTsgZG91YmxlIFJlPVIwKygxLVIwKSpjKmMqYypjKmMsVHI9MS1SZSxQPS4yNSsuNSpSZSxSUD0vUCxUUD0vKDEtClApOyByZXR1cm4gb2JqLmUgKyBmLm11bHQoZGVwdGg+MiA/IChlcmFuZDQ4KFhpKTxQID8gIHJhZGlhbmNlKHJlZmxSYXksCmRlcHRoLFhpKSpSUDpyYWRpYW5jZShSYXkoeCx0ZGlyKSxkZXB0aCxYaSkqVFApIDogcmFkaWFuY2UocmVmbFJheSwKZGVwdGgsWGkpKlJlK3JhZGlhbmNlKFJheSh4LHRkaXIpLGRlcHRoLFhpKSpUcik7fWludCBtYWluKGludCBhcmdjLCAKY2hhciAqYXJndltdKXsgaW50IHc9MTAyNCwgaD03NjgsIHNhbXBzID0gYXJnYz09MiA/IGF0b2koYXJndlsxXSkvNCA6IDE7ICAKUmF5IGNhbShWZWMoNTAsNTIsMjk1LjYpLCBWZWMoMCwtMC4wNDI2MTIsLTEpLm5vcm0oKSk7ICBWZWMgY3g9VmVjKHcqLjUxMzUvCmgpLCBjeT0oY3glY2FtLmQpLm5vcm0oKSouNTEzNSwgciwgKmM9bmV3IFZlY1t3KmhdOwojcHJhZ21hIG9tcCBwYXJhbGxlbCBmb3Igc2NoZWR1bGUoZHluYW1pYywgMSkgcHJpdmF0ZShyKSAgCmZvciAoaW50IHk9MDsgeTxoOyB5Kyspe2ZwcmludGYoc3RkZXJyLCJcclJlbmRlcmluZyglZCBzcHApICU1LjJmJSUiLApzYW1wcyo0LDEwMC4qeS8oaC0xKSk7Zm9yICh1bnNpZ25lZCBzaG9ydCB4PTAsIFhpWzNdPXswLDAseSp5Knl9OyB4PHc7CngrKylmb3IgKGludCBzeT0wLGk9KGgteS0xKSp3K3g7IHN5PDI7IHN5KyspICBmb3IgKGludCBzeD0wOyBzeDwyOyBzeCsrLCAKcj1WZWMoKSl7Zm9yKGludCBzPTA7IHM8c2FtcHM7IHMrKyl7ZG91YmxlIHIxPTIqZXJhbmQ0OChYaSksZHg9cjE8MT9zcXJ0CihyMSktMToxLXNxcnQoMi1yMSk7IGRvdWJsZSByMj0yKmVyYW5kNDgoWGkpLCBkeT1yMjwxID8gc3FydChyMiktMTogMS1zcXJ0CigyLXIyKTtWZWMgZD1jeCooKChzeCsuNStkeCkvMit4KS93LS41KStjeSooKChzeSsuNStkeSkvMit5KS8KaC0uNSkrY2FtLmQ7cj1yK3JhZGlhbmNlKFJheShjYW0ubytkKjE0MCxkLm5vcm0oKSksMCxYaSkqKDEuLwpzYW1wcyk7fWNbaV09Y1tpXStWZWMoY2xhbXAoci54KSxjbGFtcChyLnkpLGNsYW1wKHIueikpKi4yNTt9fSAKRklMRSAqZj1mb3BlbigiaW1hZ2UucHBtIiwidyIpO2ZwcmludGYoZiwiUDNcbiVkICVkXG4lZFxuIix3LGgsMjU1KTsgCmZvcihpbnQgaT0wO2k8dypoO2krKylmcHJpbnRmKGYsIiVkICVkICVkICIsdG9JbnQoY1tpXS54KSx0b0ludCgKY1tpXS55KSx0b0ludChjW2ldLnopKTt9