MLINE - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest
Author: Suryansh Kumar
Tester: Aneesh D H , John
Editorialist: Siddharth

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Basic maths

PROBLEM:

Given N points and a line y=mx+c on cartesian plane, find out number of pair of points which upon joining will make a line segment that will intersect the given line. Also the points should not lie on the line.

EXPLANATION:

The line segment formed by joining any two points will intersect the given line only when they both lie on the opposite side of the given line. Let’s say that there are P points out of N given points for which y-mx-c > 0 and Q points such that y-mc-c < 0, total number of line segments formed by these points will be P*Q

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
void _sol(){
    long long int n,m,c;
    cin >> n >> m >> c;
    long long int left=0 , right = 0;
    for(int i=0;i<n;i++){
        long long int x,y; cin >> x >> y;
        if( y - m*x - c < 0 ) left++;
        else if( y - m*x - c >0 ) right++;
    }
    cout << left*right << "\n";
    return;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1; cin >> t;
    while(t--) _sol();
}
Tester's Solution 
#include <bits/stdc++.h>
#define adj_list vector<vi>
#define endl "\n"
#define INF_INT 2e9
#define INF_LL 2e18
#define matmax 25
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define pl pair<ll, ll>
#define pll pair<ll, pair<ll, ll> >
#define vi vector<int>
#define vl vector<ll>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long int ll;
int lsone(int n)
{
    return (n&-n);
}
ll pow1(ll a, ll b)
{
    if (b == 0)
        return 1ll;
    else if (b == 1)
        return a;
    else
    {
        ll x = pow1(a, b/2);
        x *= x;
        x %= mod;
        if (b%2)
        {
            x *= a;
            x %= mod;
        }
        return x;
    }
}
ll t, n, m, c, x, y;
ll up, down;
int main()
{
    fastio; 
    cin>>t;
    while (t--) {
        up = down = 0;
        cin>>n>>m>>c;
        for (int i = 1; i <= n; i++) {

            cin>>x>>y;

            ll val = m * x + c - y;

            if (val > 0)

                up++;
            if (val < 0)
                down++;
        }
        ll ans = up * down;
        cout<<ans<<"\n";
    }
    return 0;
}
Editorialist's Solution 
 #include<bits/stdc++.h>
using namespace std;
long long m,c;
int chekr(long long x,long long y)
{
    if(y-(m*x+c)==0)
    {
        return 0;
    }
    if(y-(m*x+c)>0)
    {
        return 1;
    }
    return -1;
}
int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;cin >>t;
    while(t--)
    {
        int n;
        cin >>n>>m>>c;
        int neg=0,pos=0;
        for(int i=0;i<n;i++)
        {
            long long x,y;
            cin >>x>>y;
            if(chekr(x,y)==1)
            {
                pos++;
            }
            else if(chekr(x,y)==-1)
            {
                neg++;
            }
        }
        cout <<pos*neg<<'\n';
    }
    return 0;
}
2 Likes