Discussion on Sherlock and Geometry Challenge

Sort by

recency

|

8 Discussions

|

2 weeks ago+ 0 comments

This one was harder than I expected but I finally did it. * I calculated the distance from each point of the triangle to the circle center * if any of those distances equal the radius return "YES" * if all the distances were less than the circle radius then the triangle was inside and I returned "NO that was the easy part, then came the hard part created a function that returned true if any of the segments of a line interesect the circle. I had to use the quadratic equation for this one I had to calculate the A,B, and C of the quadratic equation. One of the variables used was the slope m of the line equation if the discriminat was less than zero, the segment doesn't touch and that function returned false if the discriminat was zero or more then it calculated the two solutions.
then with another function found out if those points lie within the segment.
That is, if that intersection was outside then there is no intersection. if any of those lines intresect, I return a "YES" so far so good. but it didn't work for all cases. then I remember that I have to take the special case when the line is vertical!!! So I added a condition for that, calculated the tww points if any, etc.... ...and after a lot of work, the damned thing worked!!!!

3 years ago+ 0 comments

OwO

//distance from p1 to p2 to the power of 2
inline long distance_p2(long p1x, long p1y, long p2x, long p2y) {
	return std::abs((p1x - p2x) * (p1x - p2x) + (p1y - p2y) * (p1y - p2y));
}

//distance from s to the nearest point on p1 - p2 to the power of 2
float distance_to_line_p2(long sx, long sy, long p1x, long p1y, long p2x, long p2y) {
	long
		e1 = distance_p2(sx, sy, p1x, p1y),//s - p1
		e2 = distance_p2(sx, sy, p2x, p2y),//s - p2
		e3 = distance_p2(p1x, p1y, p2x, p2y);//p1 - p2

	if (e3 + e1 <= e2 || e3 + e2 <= e1) {
		//if s-p1-p2 or 2-p2-p1 is an obtuse (or right) angle, the nearest point is one of the two vertices
		return std::min(e1, e2);
	}

	//else return the length of altitude (from s) to the power of two

	long long num = (long long)e1 * e3 * 4 - ((long long)e1 + e3 - e2) * ((long long)e1 + e3 - e2);

	return num / (4.0 * e3);
}

std::string solve(int x, int y, int r, const std::vector<int>& t1, const std::vector<int>& t2, const std::vector<int>& t3) {
	long r2 = r * r;
	long
		d1 = distance_p2(x, y, t1[0], t1[1]),
		d2 = distance_p2(x, y, t2[0], t2[1]),
		d3 = distance_p2(x, y, t3[0], t3[1]);

	//if one of the vertices is on the circle
	if (d1 == r2 || d2 == r2 || d3 == r2)return "YES";

	//if all vertices is inside the circle
	if (d1 < r2 && d2 < r2 && d3 < r2)return "NO";

	//if there exist at least two vertices, one inside the circle and the other on the outside of the circle
	if ((d1 < r2 || d2 < r2 || d3 < r2) && (d1 > r2 || d2 > r2 || d3 > r2)) return "YES";

	//all vertices should be outside of the circle now

	//if the nearest point of t1-t2 (from (x,y)) is inside (or on) the circle
	if (distance_to_line_p2(x, y, t1[0], t1[1], t2[0], t2[1]) <= r2)return "YES";
	//else all points of t1-t2 is outside the circle

	if (distance_to_line_p2(x, y, t1[0], t1[1], t3[0], t3[1]) <= r2)return "YES";

	if (distance_to_line_p2(x, y, t2[0], t2[1], t3[0], t3[1]) <= r2)return "YES";

	return "NO";
}

6 years ago+ 0 comments

My approach is to calculate the power of the vertices with respect to circle.

If the points are inside print NO If 2 ouside 1 inside print YES If 1 ouside 2 inside print YES If any 1 is on the circle print YES

If all the points are outside then solve the equation with the circle and check if the root lies between the end points of the line segment. I am getting an error.

6 years ago+ 0 comments

finally

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

bool isPointOnCircle(int x, int y, int r, vector<int> t){
    int x1 = (x - t[0]);
    int y1 = (y - t[1]);
    double d = sqrt(x1*x1 + y1*y1);
    return (d == r);
}

bool isPointInside(int x, int y, int r, vector<int> t){
    int x1 = (x - t[0]);
    int y1 = (y - t[1]);
    double d = sqrt(x1*x1 + y1*y1);
    return (d < r);
}

int gcd(int a, int b){
    if(a == 0)
        return b;
    return gcd(b%a, a);
}

vector<int> coefficient(vector<int> t1, vector<int> t2) {
    int a1 = t1[0];
    int a2 = t2[0];
    int b1 = t1[1];
    int b2 = t2[1];
    vector<int> v;
    int a = b1 - b2;
    int b = a2 - a1;
    int c = a1*b2 - a2*b1;
    int g = gcd(a, gcd(b, c));
    v.push_back(a/g);
    v.push_back(b/g);
    v.push_back(c/g);
    // for (int i = 0; i < v.size(); ++i){
    //     cout << v[i] << " ";
    // }
    // cout << endl;
    return v;
}

double shortestDistance(int x, int y, int r, vector<int> t1, vector<int> t2){
    vector<int> v = coefficient(t1, t2);
    double d = abs(x*v[0] + y*v[1] + v[2])/sqrt(v[0]*v[0] + v[1]*v[1]);
    return d;
}

int dist(int x1, int y1, int x2, int y2){
    return (x1 - x2)*(x1 - x2) + (y1-y2)*(y1-y2);
}

// Complete the solve function below.
bool solve(int x, int y, int r, vector<int> t1, vector<int> t2, vector<int> t3) {
    if(isPointOnCircle(x, y, r, t1) || isPointOnCircle(x, y, r, t2) || isPointOnCircle(x, y, r, t3)){
        return true;
    }
    if(isPointInside(x, y, r, t1) && isPointInside(x, y, r, t2) && isPointInside(x, y, r, t3)){
        return false;
    }
    if(isPointInside(x, y, r, t1) || isPointInside(x, y, r, t2) || isPointInside(x, y, r, t3)){
        return true;
    }
    // cout << shortestDistance(x, y, r, t1, t2) << " 45678\n";
    if(shortestDistance(x, y, r, t1, t2) <= r){
        int lineDist = dist(t1[0], t1[1], t2[0], t2[1]);
        int d1 = dist(t1[0], t1[1], x, y);
        int d2 = dist(x, y, t2[0], t2[1]);
        if(lineDist > max(d1, d2)){
            return true;
        }

        // std::vector<int> v = coefficient(t1, t2);
        // int a = v[0];
        // int b = v[1];
        // int c = v[2];
        // double x1 = (b*b*x - a*b*y - a*c)/(a*a + b*b);
        // double y1 = (a*a*y - a*b*x - b*c)/(a*a+b*b);
        // cout << a << " " << b << " " << c << "  == " << x1 << " - " << y1 << "-----\n";
        // if(min(t1[1], t2[1]) < y1 && y1 < max(t1[1], t2[1])
        //     && min(t1[0], t2[0]) < x1 && x1 < max(t1[0], t2[0])){
        //     return true;
        // }
    }
    cout << "second\n";
    if(shortestDistance(x, y, r, t1, t3) <= r){
        // std::vector<int> v = coefficient(t1, t3);
        // int a = v[0];
        // int b = v[1];
        // int c = v[2];
        // double x1 = (-1*a*b*y - a*c + b*b*x)/(a*a + b*b);
        // double y1 = (a*a*y - a*b*x - b*c)/(a*a+b*b);
        // cout << a << " " << b << " " << c << "  == " << x1 << " - " << y1 << "-----\n";
        // if(min(t1[1], t3[1]) < y1 && y1 < max(t1[1], t3[1])
        //     && min(t1[0], t3[0]) < x1 && x1 < max(t1[0], t3[0])){
        //     return true;
        // }
        int lineDist = dist(t1[0], t1[1], t3[0], t3[1]);
        int d1 = dist(t1[0], t1[1], x, y);
        int d2 = dist(x, y, t3[0], t3[1]);
        if(lineDist > max(d1, d2)){
            return true;
        }
    }
    cout << "third\n";
    if(shortestDistance(x, y, r, t3, t2) <= r){
        // std::vector<int> v = coefficient(t3, t2);
        // int a = v[0];
        // int b = v[1];
        // int c = v[2];
        // double x1 = (-1*a*b*y - a*c + b*b*x)/(a*a + b*b);
        // double y1 = (a*a*y - a*b*x - b*c)/(a*a+b*b);
        // cout << a << " " << b << " " << c << "  == " << x1 << " , " << y1 << "-----\n";
        // if(min(t3[1], t2[1]) < y1 && y1 < max(t3[1], t2[1])
        //     && min(t3[0], t2[0]) < x1 && x1 < max(t3[0], t2[0])){
        //     return true;
        // }
        int lineDist = dist(t3[0], t3[1], t2[0], t2[1]);
        int d1 = dist(t3[0], t3[1], x, y);
        int d2 = dist(x, y, t2[0], t2[1]);
        if(lineDist > max(d1, d2)){
            return true;
        }
    }
    return false;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int t;
    cin >> t;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    for (int t_itr = 0; t_itr < t; t_itr++) {
        string xyr_temp;
        getline(cin, xyr_temp);

        vector<string> xyr = split_string(xyr_temp);

        int x = stoi(xyr[0]);

        int y = stoi(xyr[1]);

        int r = stoi(xyr[2]);

        string t1_temp_temp;
        getline(cin, t1_temp_temp);

        vector<string> t1_temp = split_string(t1_temp_temp);

        vector<int> t1(2);

        for (int i = 0; i < 2; i++) {
            int t1_item = stoi(t1_temp[i]);

            t1[i] = t1_item;
        }

        string t2_temp_temp;
        getline(cin, t2_temp_temp);

        vector<string> t2_temp = split_string(t2_temp_temp);

        vector<int> t2(2);

        for (int i = 0; i < 2; i++) {
            int t2_item = stoi(t2_temp[i]);

            t2[i] = t2_item;
        }

        string t3_temp_temp;
        getline(cin, t3_temp_temp);

        vector<string> t3_temp = split_string(t3_temp_temp);

        vector<int> t3(2);

        for (int i = 0; i < 2; i++) {
            int t3_item = stoi(t3_temp[i]);

            t3[i] = t3_item;
        }

        bool r1 = solve(x, y, r, t1, t2, t3);
        string result = (r1)? "YES" : "NO";
        fout << result << "\n";
    }

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

6 years ago+ 0 comments

this is my code which I wrote in 5-6 hours can someone point out what am i missing because this is really frustrating they have given a testcase and inside that testcase there are 30000 testcases :( instead they should have given 10 seprate testcases :(

#include <bits/stdc++.h>
using namespace std;

//int dist();

int distance(int x,int y,int x1,int y1,int x2,int y2)
{
    float x3=0.0,y3=0.0,temp=0.0,temp1=0.0;

    float slope = (y2-y1)/(1.0*(x2-x1));

    //cout<<slope<<endl;

    temp = y1-y-x1*(slope)-x*(1.0/slope);
    temp1 = -(1.0/slope)-slope;
    float x_cor = temp/(1.0*temp1) ;
    float y_cor = y1+ slope*(x_cor-x1);


    float dist = 0.0;

    dist = (x-x_cor)*(x-x_cor)+(y-y_cor)*(y-y_cor);

    return dist;  

}

// Complete the solve function below.
string solve(int x, int y, int r, vector<int> t1, vector<int> t2, vector<int> t3) {

      
    int count1=0,count2=0,count3=0;
    
    if( (t1[0]-x)*(t1[0]-x)+(t1[1]-y)*(t1[1]-y) < r*r ) count1++;
    if( (t2[0]-x)*(t2[0]-x)+(t2[1]-y)*(t2[1]-y) < r*r ) count1++;
    if( (t3[0]-x)*(t3[0]-x)+(t3[1]-y)*(t3[1]-y) < r*r ) count1++;

    if( (t1[0]-x)*(t1[0]-x)+(t1[1]-y)*(t1[1]-y) > r*r ) count2++;
    if( (t2[0]-x)*(t2[0]-x)+(t2[1]-y)*(t2[1]-y) > r*r ) count2++;
    if( (t3[0]-x)*(t3[0]-x)+(t3[1]-y)*(t3[1]-y) > r*r ) count2++;

    if( (t1[0]-x)*(t1[0]-x)+(t1[1]-y)*(t1[1]-y) == r*r ) count3++;
    if( (t2[0]-x)*(t2[0]-x)+(t2[1]-y)*(t2[1]-y) == r*r ) count3++;
    if( (t3[0]-x)*(t3[0]-x)+(t3[1]-y)*(t3[1]-y) == r*r ) count3++;


    //cout<<count1<<" "<<count2<<endl;


    
    float point_x=0.0,point_y=0.0,temp=0.0,dist=0.0;
    

    if(count3 != 0 ) return "YES";

    if(count1 == 3 )  return "NO";

    if(count1 == 1 && count2 == 2) return "YES";

    if(count1 == 2 && count2 == 1) return "YES";
    
    else if (count2 == 3)  
    {
        float dist1 = distance(x,y,t1[0],t1[1],t2[0],t2[1]);
        float dist2 = distance(x,y,t1[0],t1[1],t3[0],t3[1]);
        float dist3 = distance(x,y,t2[0],t2[1],t3[0],t3[1]);

        //float test4 = dist(4,0,0,0,4,4);
        
        if(dist1 <= r*r*1.0 ) return "YES";
        if(dist2 <= r*r*1.0 ) return "YES";
        if(dist3 <= r*r*1.0)  return "YES";
        else return "NO"; 
            
            
    }

    else return "YES";
    
}

int main()
{
    int t;

    cin>>t;

    

    
    vector<string> res;

    string result;

    for(int i=0; i<t; i++)
    {
        int x,y,r;

        int x1,y1,x2,y2,x3,y3;

        vector<int> t1,t2,t3;

        cin>>x>>y>>r;
        cin>>x1>>y1;
        t1.push_back(x1);
        t1.push_back(y1);
        cin>>x2>>y2;
        t2.push_back(x2);
        t2.push_back(y2);
        cin>>x3>>y3;
        t3.push_back(x3);
        t3.push_back(y3);

        result = solve(x,y,r,t1,t2,t3);
        res.push_back(result);
        
            
    }    
    
    for(int i=0; i<t; i++)
    {
        cout<<res[i]<<endl;
    }
return 0;
}

Sort by

|

8 Discussions

|

Cookie support is required to access HackerRank