Hi guys,
I gave the Newton's coding challenge held today and could solve only 4, I got 15+ WAs on 5th and couldn't solve the 6th problem. Can anyone please tell me the solution for the last problem and if possible tell me the error in my code for 5th problem?
Also feel free to use comment section to discuss other solutions as well.
//Nightmare05
include<bits/stdc++.h>
using namespace std;
define sp << " " <<
define mod 1000000007
define mp make_pair
define pb push_back
define int long long
define double long double
define INF (1e18+13)
define PI 3.1415926535898
int power(int p,int j) { int res=1; p=p%mod; while(j>0) { if(j&1) res=(res*p)%mod; j=j>>1; p=(p*p)%mod; } return res; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int dice(int d,int p) { uniform_int_distribution uid(d,p);//specify l and s. return uid(rng) ; } /* int read() { int cc = getc(stdin); for (;cc < '0' || cc > '9';) cc = getc(stdin); int ans = 0; for (;cc >= '0' && cc <= '9';) { ans = ans * 10 + cc — '0'; cc = getc(stdin); } return ans; }
inline void print(int n) { if (n == 0) { putchar('0'); putchar('\n'); } else if (n == -1) { putchar('-'); putchar('1'); putchar('\n'); } else { char buf[20]; buf[19] = '\n'; int i = 18; while (n) { buf[i--] = n % 10 + '0'; n /= 10; } while (buf[i] != '\n') putchar(buf[++i]); } }
int n;
vector<vector> mat_mul(vector<vector> a,vector<vector> b) { int n=5; vector<vector> ans2(n,vector(n,0)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { for(int ans2=0;ans2<n;ans2++) { ans2[i][j]+=((a[i][ans2]*b[ans2][j])%mod); ans2[i][j]%=mod; } } } return ans2; }
vector<vector> pow_mat(vector<vector> mat_a,int p) { if(p==1) return mat_a; vector<vector> temp=pow_mat(mat_a,p/2); vector<vector> res=mat_mul(temp,temp); if(p&1) res=mat_mul(res,mat_a); return res; } */
double s(double m1,double m2,double c1,double c2,double c3,double c4) { double x1,x2,x3,x4,y1,y2,y3,y4; x1=(c2-c1)/(m1-m2); x2=(c3-c2)/(m2-m1); x3=(c4-c3)/(m1-m2); x4=(c1-c4)/(m2-m1); y1=m1*x1+c1; y2=m2*x2+c2; y3=m1*x3+c3; y4=m2*x4+c4; double d[4]; d[0]=(y2-y1)*(y2-y1)+(x2-x1)*(x2-x1); d[1]=(y3-y2)*(y3-y2)+(x3-x2)*(x3-x2); d[2]=(y4-y3)*(y4-y3)+(x4-x3)*(x4-x3); d[3]=(y1-y4)*(y1-y4)+(x1-x4)*(x1-x4); sort(d,d+4); if(abs(d[3]-d[0])<0.01) return sqrt((d[0]+d[3])/2)+26.0; else return -1; }
int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("elimination_validation_input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int t; cin >> t; while(t--) { double dp=-1; double x1,x2,x3,x4,y1,y2,y3,y4; pair<double,double> a[4]; cin >> a[0].first >> a[0].second >> a[1].first >> a[1].second >> a[2].first >> a[2].second >> a[3].first >> a[3].second; for(int j=0;j<6;j++) { if(j==1||j==3||j==5) swap(a[2],a[3]); if(j==2||j==4) swap(a[1],a[3]); x1=a[0].first; y1=a[0].second; x2=a[1].first; y2=a[1].second; x3=a[2].first; y3=a[2].second; x4=a[3].first; y4=a[3].second; for(double i=0.0;i<=1.0;i+=0.0001) { double m1=i*PI; m1=tan(m1); double c1=y1-m1*x1,c3=y3-m1*x3; double m2=-1/m1; if(m1==0.00000) m2=tan(PI/2); double c2=y2-m2*x2,c4=y4-m2*x4; int h=1; double p[3]; p[0]=y2-m1*x2-c1; p[1]=y3-m1*x3-c1; p[2]=y4-m1*x4-c1; if(abs(p[0])>abs(p[1])||abs(p[2])>abs(p[1])) h=0; sort(p,p+3); for(int z=0;z<3;z++) if(abs(p[z])<0.0000000001) h=0; if(p[0]*p[2]<0) h=0; p[0]=y1-m2*x1-c2; p[1]=y3-m2*x3-c2; p[2]=y4-m2*x4-c2; if(abs(p[0])>abs(p[2])||abs(p[1])>abs(p[2])) h=0; sort(p,p+3); for(int z=0;z<3;z++) if(abs(p[z])<0.0000000001) h=0; if(p[0]*p[2]<0) h=0; p[0]=y2-m1*x2-c3; p[1]=y1-m1*x1-c3; p[2]=y4-m1*x4-c3; if(abs(p[0])>abs(p[1])||abs(p[2])>abs(p[1])) h=0; sort(p,p+3); for(int z=0;z<3;z++) if(abs(p[z])<0.0000000001) h=0; if(p[0]*p[2]<0) h=0; p[0]=y2-m2*x2-c4; p[1]=y3-m2*x3-c4; p[2]=y1-m2*x1-c4; if(abs(p[1])>abs(p[0])||abs(p[2])>abs(p[0])) h=0; sort(p,p+3); for(int z=0;z<3;z++) if(abs(p[z])<0.0000000001) h=0; if(p[0]*p[2]<0) h=0; if(h) dp=max(dp,s(m1,m2,c1,c2,c3,c4)); } } if(dp<26) cout << -1 << endl; else cout << fixed << setprecision(2) << dp << endl; } return 0; }
I would be really thankful if someone can point out, exactly what edge cases did I miss!
Cheers!!!