DragonKoko's blog

By DragonKoko, 6 years ago, In English

so i tried to solve this two problem and they both got WA test 2

here's the problems 2012-2013 Waterloo Local Contest, 13 October, 2012 :

so i want to know the main idea of the both gym problems if possible and what is the trick in the second test case ?

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Here's the approach to the problem E:

Overview:

-Imagine if we remove one of the edges of length x from the given tetrahedron. Now we are left with two triangular faces with a common side as a hinge.

-Now try to find the lowerbound and upperbound for the edge you just removed using some trigonometry for each permutation of remaining five edges which make up two triangular faces.

-If x fits within lowerbound and upperbound of any permutation, print "YES" else print "NO".

Here's my code:


/* _ _oo0oo_ o8888888o 88" . "88 (| -_- |) 0\ = /0 ____/`---'\____ / \\| |// \ / \\||| /:\ |||// \ / _||||| -:- |||||- \ | | \\\ \-/ /// | | | \_| ''\---/'' |_/ | \ .-\__ '-' ___/-. / ____'. .' /--.--\ `. .'_____ /"" '< `.___\_<|>_/___.' >' "" \ | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `_. \_ __\ /__ _/ .-` / _/ `-.____`.___ \_____/___.-`___.-' ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ JENISH MONPARA S. IIT PATNA I_LOVE_ADITI_GOEL ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/ #include <bits/stdc++.h> using namespace std; const long double PI = 3.141592653589793; const long double DEL = 1e-12; const int mod = 1000000007; const int LIM = 100005; #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define mpq priority_queue<int,vector<int>,greater<int>> #define deb(a) cerr << #a << ": " << a << endl #define ftt cin>>t;for(int tt=1;tt<=t;++tt) #define Rev(v) reverse(v.begin(),v.end()) #define Sort(v) sort(v.begin(),v.end()) #define mem(a,b) memset(a,b,sizeof(a)) #define umii unordered_map<int,int> #define all(a) a.begin() , a.end() #define vvi vector<vector<int>> #define pq priority_queue<int> #define sqr(a) (((a) * (a))) #define double long double #define dbg cout<<"\nhi\n" #define pii pair<int,int> #define mii map<int,int> #define vb vector<bool> #define vi vector<int> #define nl cout<<"\n" #define pb push_back #define int long long #define sp <<" "<< #define ss second #define ff first int fpow(int x, int n) { int res = 1; while(n){ if(n&1){ res = res * x % mod; } x = x * x % mod; n>>=1; } return res; } int gcd(int a,int b) { if(b == 0) { return a; } return gcd(b,a % b); } void sieve(int n) { bool prime[5*LIM]; memset(prime, true, sizeof(prime)); int rootn = (int)sqrt(n); for (int p = 2; p <= rootn; p++) { if (prime[p] == true) { for (int i = p*p; i <= n; i += p) { prime[i] = false; } } } prime[1] = 0; } int cnt, sum, mid, mx, mn, ans, a[2*LIM]; int n, m, d, p, q, t, i, j, k, l, r, x, y, z; bool f, f1, f2; string s; //******************************************* CHECK CONSTRAINTS ************************************************** double ar(int x,int y,int z) { double s = (x+y+z*1.00)/2.00; return sqrt(s*(s-x)*(s-y)*(s-z)); } bool ok(int x,int y,int z) { if(x+y <= z || y+z<=x || z+x<=y) { return false; } return true; } int32_t main() { fio; ftt { vi a(6); for(i=0;i<5;i++) { cin>>a[i]; } cin>>x; Sort(a); f = 0; do { if(ok(a[0],a[3],a[4])&&ok(a[2],a[1],a[4])) { // for upper double alpha = acos( (sqr(a[0])+sqr(a[4])-sqr(a[3]))/(2.0*a[0]*a[4])); double beta = acos((sqr(a[1])+sqr(a[4])-sqr(a[2]))/(2.0*a[1]*a[4])); beta += alpha; double r = sqrt(sqr(a[0])+sqr(a[1])-2.0*a[0]*a[1]*cos(beta)); // for lower alpha = acos((sqr(a[4])+sqr(a[2])-sqr(a[1]))/(2.0*a[4]*a[2])); beta = acos((sqr(a[4])+sqr(a[3])-sqr(a[0]))/(2.0*a[4]*a[3])); beta = alpha - beta; double l = sqrt(sqr(a[3])+sqr(a[2])-2.0*a[2]*a[3]*cos(beta)); if(l < x && x < r) { f = 1; break; } } }while(next_permutation(all(a))); if(f) { cout<<"YES\n"; } else { cout<<"NO\n"; } } }