zoj 2928 Mathematical contest...

zoj 2928 Mathematical contest...

#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <stack>#include <string>#include <map>#include <time.h>#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define CLR(x) x.clear()#define ph(x) push(x)#define pb(x) push_back(x)#define Len(x) x.length()#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))#define MP(x,y) make_pair(x,y)#define EPS 1e-12#define FOR0(i,x) for(i=0;i<x;i++)#define FOR1(i,x) for(i=1;i<=x;i++)#define FOR(i,a,b) for(i=a;i<=b;i++)#define FORL0(i,a) for(i=a;i>=0;i--)#define FORL1(i,a) for(i=a;i>=1;i--)#define FORL(i,a,b)for(i=a;i>=b;i--)#define rush() int CC;for(scanf("%d",&CC);CC--;)#define Rush(n) while(scanf("%d",&n)!=-1)using namespace std;void RD(int &x){scanf("%d",&x);}void RD(i64 &x){scanf("%lld",&x);}void RD(u64 &x){scanf("%I64u",&x);}void RD(u32 &x){scanf("%u",&x);}void RD(double &x){scanf("%lf",&x);}void RD(int &x,int &y){scanf("%d%d",&x,&y);}void RD(i64 &x,i64 &y){scanf("%lld%lld",&x,&y);}void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}void RD(i64 &x,i64 &y,i64 &z){scanf("%lld%lld%lld",&x,&y,&z);}void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}void RD(char &x){x=getchar();}void RD(char *s){scanf("%s",s);}void RD(string &s){cin>>s;}void PR(int x) {printf("%dn",x);}void PR(int x,int y) {printf("%d %dn",x,y);}void PR(i64 x) {printf("%lldn",x);}void PR(i64 x,i64 y) {printf("%lld %lldn",x,y);}void PR(u32 x) {printf("%un",x);}void PR(u64 x) {printf("%llun",x);}void PR(double x) {printf("%.8lfn",x);}void PR(double x,double y) {printf("%.3lf %.3lfn",x,y);}void PR(char x) {printf("%cn",x);}void PR(char *x) {printf("%sn",x);}void PR(string x) {cout<<x<<endl;}const int mod=10007;const i64 inf=((i64)1)<<40;const double dinf=1000000000000000000.0;const int INF=100000000;const int N=1005;int sgn(double x){ if(x>EPS) return 1; if(x<-EPS) return -1; return 0;}struct point{ double x,y; point(){} point(double _x,double _y) { x=_x; y=_y; } void get() { RD(x); RD(y); } point operator+(point a) { return point(x+a.x,y+a.y); } point operator-(point a) { return point(x-a.x,y-a.y); } double operator*(point a) { return x*a.y-y*a.x; } point operator*(double t) { return point(x*t,y*t); } double operator^(point a) { return x*a.x+y*a.y; } double len() { return sqrt(x*x+y*y); } void print() { printf("%.3lf %.3lfn",x+EPS,y+EPS); }};double len(point a){ return a.len();}struct point3{ double x,y,z; point3(){} point3(double _x,double _y,double _z) { x=_x; y=_y; z=_z; } void get() { RD(x); RD(y); RD(z); } point3 operator+(point3 a) { return point3(x+a.x,y+a.y,z+a.z); } point3 operator-(point3 a) { return point3(x-a.x,y-a.y,z-a.z); } point3 operator*(point3 a) { return point3(y*a.z-z*a.y,z*a.x-x*a.z,x*a.y-y*a.x); } point3 operator*(double t) { return point3(x*t,y*t,z*t); } double operator^(point3 a) { return x*a.x+y*a.y+z*a.z; } point3 operator/(double t) { return point3(x/t,y/t,z/t); } double len() { return sqrt(x*x+y*y+z*z); } void print() { printf("%.3lf %.3lf %.3lfn",x+EPS,y+EPS,z+EPS); }};double len(point3 a){ return a.len();}int n;point3 p[N],d[N];int main(){ Rush(n) { int i,j,k; FOR1(i,n) p[i].get(); point3 ans=point3(0,0,0),cur; double step=2000,Min=dinf,temp; int x=0; FOR(i,-1,1) FOR(j,-1,1) FOR(k,-1,1) { d[x++]=point3(i,j,k); } while(step>EPS) { FOR0(i,x) { temp=0; cur=ans+d[i]*step; FOR1(j,n) temp+=(p[j]-cur).len(); if(sgn(temp-Min)==-1) ans=cur,Min=temp; } step*=0.99; } ans.print(); }}