ECJAN20I - Editorial

Practice

Contest

Author: Soham Chakrabarti

DIFFICULTY:

Easy

PREREQUISITES:

Convex Hull Trick (Graham Scan)

PROBLEM:

Given N points on a 2-d plane, Find the smallest convex polygon that contains all the points of it.

EXPLANATION:

This is a direct algorithm approach problem. Find the number of points, compare it with P poles and print YES or NO accordingly.

Sources : video, article, code

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.

this is my code

#include<bits/stdc++.h>
using namespace std;
#define int long long int
struct point{
int x,y;
bool operator < (point &O){
if(O.x==x) return y<O.y;
else return x<O.x;
}
bool operator == (point &O)
{
return (x==O.x&&y==O.y);
}
};
bool cw(point a, point b,point c)
{
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
}
bool ccw(point a, point b,point c)
{
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
}
void convex_hull(vector &p,int s)
{
if(p.size()<=2) return;
sort(p.begin(),p.end());
int i,n=p.size();
point p1=p[0],p2=p[n-1];
vector up,down ;
up.push_back(p[0]);down.push_back(p[0]);
for(i=1;i<n;i++)
{
if(i==n-1|| !ccw(p1,p[i],p2))
{
while(up.size()>2&&ccw(up[up.size()-2],up[up.size()-1],p[i]))
{
up.pop_back();
}
up.push_back(p[i]);
}
if(i==n-1||!cw(p1,p[i],p2))
{
while(down.size()>2&&ccw(down[down.size()-2],down[down.size()-1],p[i]))
{
down.pop_back();
}
down.push_back(p[i]);
}
}
p.clear();
for(i=0;i<up.size();i++)
p.push_back(up[i]);
for(i=0;i<down.size();i++)p.push_back(down[i]);
// sort(p.begin(),p.end());
// p.resize(unique(p.begin(),p.end())-p.begin());
if(s>=up.size()+down.size()-2) cout<<“YES\n”;
else cout<<“NO\n”;
}
void solve()
{
int n,i,s;
cin>>n>>s;
vector p(n);
for(i=0;i<n;i++) cin>>p[i].x>>p[i].y;
convex_hull(p,s);
// for(int i=0;i<p.size();i++)cout<<p[i].x<<" “<<p[i].y<<”\n";
}
main()
{
int t;
cin>>t;
while (t–){
solve();
}
}
where have i gone wrong ??