OJ Board

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
using namespace std;

bool cmp(pair<int,int> p1,pair<int,int> p2)
{
	int temp=p1.second*p2.first-p1.first*p2.second;
	if(temp==0.0)
		return p1.second<p2.second;
	else
		return (temp<=0.0);
	/*else if(temp>0.0)
		return 0;
	else
		return 1;*/
}

bool cmp1(pair<int,int>v1 ,pair<int,int> v2)
{
	if(v2.second==v1.second)
		return v1.first<v2.first;
	else
		return v1.second<v2.second;
}

pair<int,int> next_to_top(vector<pair<int,int> > s)
{
	pair<int,int> p1(0,0);
	if(s.size()>=2)
	{
		vector<pair<int,int> >::iterator i=s.end()-2;
		p1=*i;
	}
	return p1;
}

bool nonleftturn(pair<int,int> p1,pair<int,int> p2,pair<int,int> p3)
{
	pair<int,int> v1(p3.first-p1.first,p3.second-p1.second),v2(p2.first-p1.first,p2.second-p1.second);
	return ((v1.first*v2.second-v1.second*v2.first)>=0);
	
}

vector<pair<int,int> > convexhull(vector<pair<int,int> > v,int n)
{
	vector<pair<int,int> > vertex(n);
	pair<int,int> shift=*(min_element(v.begin(),v.end(),cmp1));
	for(int i=0;i<n;i++)
	{  
		vertex[i].first=v[i].first-shift.first;
		vertex[i].second=v[i].second-shift.second;
	}
	
/*	for(int i=0;i<vertex.size();i++)
	{
		cout<<vertex[i].first<<" "<<vertex[i].second<<endl;
	}*/
	sort(vertex.begin(),vertex.end(),cmp);
	/*for(int i=0;i<vertex.size();i++)
	{
		cout<<vertex[i].first+shift.first<<" "<<vertex[i].second+shift.second<<endl;
	}*/
		
	vector<pair<int,int> > s;
	s.push_back(vertex[0]);
	s.push_back(vertex[1]);
	s.push_back(vertex[2]);
	for(int i=3;i<n;i++)
	{
		while (s.size()>=2 && nonleftturn(next_to_top(s),s.back(),vertex[i]))
		{
			s.pop_back();
		}
		s.push_back(vertex[i]);
	}	
	for(vector<pair<int,int> >::iterator i=s.begin();i!=s.end();i++)
	{
		(*i).first+=shift.first;
		(*i).second+=shift.second;
	}
	return s;	
}




int main()
{
	int m;
	cin>>m;
	cout<<m<<endl;
	while(m--)
	{

		int n;
		cin>>n;
		vector<pair<int,int> > kingdom(n-1);
		for(int i=0;i<n-1;i++)
		{
			cin>>kingdom[i].first;
			cin>>kingdom[i].second;
		}
		int waste1,waste2,delim;
		cin>>waste1>>waste2;
		if(m!=0)
			cin>>delim;

		vector<pair<int,int> > v=convexhull(kingdom,n-1);
		cout<<v.size()+1<<endl;
		for(int i=0;i<v.size();i++)
		{
			cout<<v[i].first<<" "<<v[i].second<<endl;
		}
		cout<<v[0].first<<" "<<v[0].second<<endl;
		if(m!=0)
			cout<<delim<<endl;

	}	
	return 0;
}

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
using namespace std;

bool cmp(pair<int,int> p1,pair<int,int> p2)
{
	int temp=p1.second*p2.first-p1.first*p2.second;
	if(temp==0)
		if(p1.second==p2.second)
			return p1.first<p2.first;
		else
			return p1.second<p2.second;
	else
		return (temp<=0);
	/*else if(temp>0.0)
		return 0;
	else
		return 1;*/
}

bool cmp1(pair<int,int>v1 ,pair<int,int> v2)
{
	if(v2.second==v1.second)
		return v1.first<v2.first;
	else
		return v1.second<v2.second;
}

pair<int,int> next_to_top(vector<pair<int,int> > s)
{
	pair<int,int> p1(0,0);
	if(s.size()>=2)
	{
		vector<pair<int,int> >::iterator i=s.end()-2;
		p1=*i;
	}
	return p1;
}

bool nonleftturn(pair<int,int> p1,pair<int,int> p2,pair<int,int> p3)
{
	pair<int,int> v1(p3.first-p1.first,p3.second-p1.second),v2(p2.first-p1.first,p2.second-p1.second);
	return ((v1.first*v2.second-v1.second*v2.first)>=0);
	
}

vector<pair<int,int> > convexhull(vector<pair<int,int> > v,int n)
{
	if(v.size()<3)
	{
		if(v.size()==2 && v[1]==v[0])
			
			{
				vector<pair<int,int> > temp;
				temp.push_back(v[0]);
				return temp;

			}

		else
		{
			return v;
		
		}
	}
	vector<pair<int,int> > vertex(n);
	pair<int,int> shift=*(min_element(v.begin(),v.end(),cmp1));
	for(int i=0;i<n;i++)
	{  
		vertex[i].first=v[i].first-shift.first;
		vertex[i].second=v[i].second-shift.second;
	}
	
/*	for(int i=0;i<vertex.size();i++)
	{
		cout<<vertex[i].first<<" "<<vertex[i].second<<endl;
	}*/
	sort(vertex.begin(),vertex.end(),cmp);
	for(int i=0;i<vertex.size();i++)
	{
		cout<<vertex[i].first+shift.first<<" "<<vertex[i].second+shift.second<<endl;
	}
		
	vector<pair<int,int> > s;
	s.push_back(vertex[0]);
	s.push_back(vertex[1]);
	s.push_back(vertex[2]);
	for(int i=3;i<n;i++)
	{
		while (s.size()>=2 && nonleftturn(next_to_top(s),s.back(),vertex[i]))
		{
			s.pop_back();
		}
		s.push_back(vertex[i]);
	}	
	for(vector<pair<int,int> >::iterator i=s.begin();i!=s.end();i++)
	{
		(*i).first+=shift.first;
		(*i).second+=shift.second;
	}
	return s;	
}

int main()
{
	int m;
	cin>>m;
	cout<<m<<endl;
	while(m--)
	{
		int n;
		cin>>n;
		vector<pair<int,int> > kingdom(n-1);
		for(int i=0;i<n-1;i++)
		{
			cin>>kingdom[i].first;
			cin>>kingdom[i].second;
		}
		int waste1,waste2,delim;
		cin>>waste1>>waste2;
		if(m!=0)
			cin>>delim;
		vector<pair<int,int> > v=convexhull(kingdom,n-1);
		cout<<v.size()+1<<endl;
		for(int i=0;i<v.size();i++)
		{
			cout<<v[i].first<<" "<<v[i].second<<endl;
		}
		cout<<v[0].first<<" "<<v[0].second<<endl;
		if(m!=0)
			cout<<delim<<endl;
	}	
	return 0;
}

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
 #include<set>
#include<complex>
using namespace std;

template  <class type1> type1 cross(const complex <type1>  &a, const complex <type1>  &b) { return imag(conj(a) * b); }

 bool cmp(const complex <int>  &a, const complex <int>  &b)
{
	if(a.imag()==b.imag())
		return a.real() <b.real();
	else
		return a.imag()<b.imag();
}

bool isequal(const complex <int>  &a, const complex <int>&b)
{
	return (a.real()==b.real() && a.imag()==b.imag());
}


template < class type1> void display(vector<complex<type1> > v){
	for(unsigned  i=0;i<v.size();i++)
	{
		cout<<v[i]<<endl;
	}

}

bool polarcmp(complex <int> a,complex<int> b)
{
	int c=cross(a,b);
	if(c>0)
		return 1;
	else 
		return 0;
		
}
template < class type1> vector<complex<type1> > convexhull(vector<complex<type1> > v)
{
	sort(v.begin(),v.end(),cmp);	
	v.erase(unique(v.begin(),v.end(),isequal),v.end());
	complex<type1> p=v[0];
	for(unsigned i=0;i<v.size();i++)
		v[i]=v[i]-=p;
	stable_sort(v.begin()+1,v.end(),polarcmp);
	vector<complex<type1> > s;
	s.push_back(v[0]);
	s.push_back(v[1]);
	for(unsigned  i=2;i<v.size();i++)
	{
		while(cross(s.back()-s[s.size()-2],v[i]-s.back())<=0)
		{
			s.pop_back();
		}
		s.push_back(v[i]);
	}
	
	for(unsigned i=0;i<s.size();i++)
	{
		s[i]+=p;
	}	
	return s;
}

int main()
{
	int k;
	cin>>k;
	cout<<k<<endl;
	while(k--)
	{	
		int n;
		cin>>n;
		vector<complex<int> > p(n);
		for(int i=0;i<n;i++)
		{
			int x,y;
			cin>>x>>y;
			complex <int> temp(x,y);
			p[i]=temp;
		}
		int delimiter;
		if(k)
		cin>>delimiter;	
		vector<complex<int> > v=convexhull(p);			
		cout<<v.size()+1<<endl;
		for(unsigned  i=0;i<v.size();i++)
		{
			cout<<v[i].real()<<" "<<v[i].imag()<<endl;
		}
		cout<<v[0].real()<<" "<<v[0].imag()<<endl;
		if(k)
			cout<<delimiter<<endl;
	}
	return 0;
}

Code: Select all

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
#define SQR(n) (n)*(n)

struct Point{
	int x, y;
	Point(int a = 0, int b = 0) : x(a), y(b){}
	static Point comp;
	int operator - (Point p){
		return SQR(x - p.x) + SQR(y - p.y);
	}
	bool operator < (const Point p)const{
		int left = (comp.y - y)
			* (comp.x - p.x);
		int right = (comp.y - p.y)
			* (comp.x - x);
		if (left < right) return true;
		if (left > right) return false;
		left = comp - *this;
		right = comp - p;
		if (left > right) return true;
		return false;
	}
};

Point Point::comp = Point(9999999, 9999999);

inline int area(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);
}
vector<Point> grahamScan(vector<Point> points) {
	for (int i = 0; i < points.size(); i++) if (Point::comp.y > points[i].y ||
		(Point::comp.y == points[i].y && Point::comp.x > points[i].x))
		Point::comp = points[i];
	vector<Point> ret; ret.reserve(points.size());
	sort(points.begin(), points.end());
	ret.push_back(points.back());
	ret.push_back(points[0]);
	for (int i = 1, t = 1; i < points.size(); i++) {
		int area_ = area(ret[ret.size() - 2], ret[ret.size() - 1],
			points[i]);
		while (area_ <= 0) {
			Point a = ret[ret.size() - 2], b = ret[ret.size() - 1], c = points[i];
			if (area_ == 0 && (c.x - a.x) * (c.x - b.x) <= 0 && (c.y - a.y) * (c.y - b.y) <= 0){
				t = 0;
				break;
			}
			ret.pop_back();
			area_ = area(ret[ret.size() - 2], ret.back(), points[i]);
		}
		if (t) ret.push_back(points[i]); t++;
	}
	return ret;
}
int main(){
	int n;
	cin >> n;
	cout << n << endl;
	for (int i = 0; i < n; i++){
		int t;
		cin >> t;
		vector<Point> points;
		for (int j = 1; j < t; j++){
			int a, b;
			cin >> a >> b;
			points.push_back(Point(a, b));
		}
		cin >> t >> t;
		vector<Point> ret = grahamScan(points);
		cout << ret.size() << endl;
		for (int j = 0; j < ret.size(); j++){
			cout << ret[j].x << " " << ret[j].y << endl;
		}
		if (i < n - 1){
			cin >> t;
			cout << -1 << endl;
		}
	}
}

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
#include <sstream>
#include <climits>
#include <list>
#include <string>
#include <map>
using namespace std;

/*------- Constants---- */
#define MX 1000006
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define EPS 1e-9
#define PI acos(-1)

/* -------Global Variables ------ */
ll euclid_x,euclid_y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;

/*------ template functions ------ */
template < class T > inline T gcd(T a , T b ) { if(b==0) return a; else return gcd(b, a%b);}
template < class T > inline T lcm(T a , T b ) { return  a*b / gcd(a, b);}
template < class T > inline void extended_euclid_returning_gcd(T a,T b){ if(b==0){d = a;euclid_x=1;euclid_y=0;} else {extended_euclid_returning_gcd(b, a%b);
	T x1 = euclid_y; T y1 = euclid_x - (a / b) * euclid_y ; euclid_x = x1 ; euclid_y = y1 ;}}
template < class T > inline T absolute(T a ) { if(a>0) return a; else return -a;}
template < class T > inline T reverse_num( T a ){ T x=0,tmp = a; while(tmp) { x=10*x+ tmp % 10; tmp/=10;} return x;}
template <class T > inline T big_mod(T base, T power){ T res=1; while (power) { if(power&1){ res*=base; power--;} base =base *base; power/=2;} return res;}
template < class T > inline T mul_inv( T a , T b){T b0 = b, t, q; T x0 = 0, x1 = 1; if (b == 1) return 1;while (a > 1) { q = a / b;
        t = b, b = a % b, a = t; t = x0, x0 = x1 - q * x0, x1 = t; } if (x1 < 0) x1 += b0; return x1;
}




struct Point
{
        long long x;
        long long y;
        bool del;
        Point(){}
        bool operator == (const Point &a)
        {
                if(a.x==x && a.y==y) return 1;
                return 0;
        }
};

// A globle point needed for  sorting points with reference to the first point
// Used in compare function of qsort()
Point p0;

// A utility function to find next to top in a stack
Point nextToTop(stack<Point> &S)
{
        Point p = S.top();
        S.pop();
        Point res = S.top();
        S.push(p);
        return res;
}

// A utility function to swap two points
void swap(Point &p1, Point &p2)
{
        Point temp = p1;
        p1 = p2;
        p2 = temp;
}

// A utility function to return square of distance between p1 and p2
ll dist(Point p1, Point p2)
{
        return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
        ll  val = (q.y - p.y) * (r.x - q.x) -
        (q.x - p.x) * (r.y - q.y);
        
        if (val == 0) return 0;  // colinear
        return (val > 0)? 1: 2; // clock or counterclock wise
}

// A function used by library function qsort() to sort an array of
// points with respect to the first point
int compare(const void *vp1, const void *vp2)
{
        Point *p1 = (Point *)vp1;
        Point *p2 = (Point *)vp2;
        
        // Find orientation
        int o = orientation(p0, *p1, *p2);
        if (o == 0){
                if( dist(*p1, p0) < dist(*p2, p0) ){
                        p1->del = true;
                        return -1;
                }
                else {
                        p2->del = true;
                        return 1;
                }
        
        }
        return (o == 2)? -1: 1;
}

vector<Point> points;
int squash(int n )
{
        int i = 0, j = 0;
        for (; i < n ; i ++) {
                if(points[i].del == false ){
                        swap(points[i], points[j]);
                        j ++;
                }
        }
        return j;
}

ll check(const Point &O, const Point &A, const Point &B)
{
        return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
template <class T> double getdist(T a, T b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}
bool comp_angle(const Point &a, const Point &b)
{
        if(check(p0, a, b) > 0)
                return true;
        else if(check(p0, a, b) == 0)
                return getdist(p0, a) < getdist(p0, b);
        return false;
}
// Prints convex hull of a set of n points.
int convexHull( int n , vector<Point > & hull)
{
        // Find the bottommost point
        ll ymin = points[0].y, min = 0;
        for (int i = 1; i < n; i++)
        {
                ll y = points[i].y;
                
                // Pick the bottom-most or chose the left most point in case of tie
                if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
                        ymin = points[i].y, min = i;
        }
        
        // Place the bottom-most point at first position
        swap(points[0], points[min]);
        
        // Sort n-1 points with respect to the first point.  A point p1 comes
        // before p2 in sorted ouput if p2 has larger polar angle (in
        // counterclockwise direction) than p1
        p0 = points[0];
        qsort(&points[1], n-1, sizeof(Point), compare);
        
        // This line gave me WA ? But don't know why >???
        n = squash(n);

        // Create an empty stack and push first three points to it.
       
        
        stack<Point> S;
        
        S.push(points[0]);
        S.push(points[1]);
        
        // Process remaining n-3 points
        for (int i = 2; i < n; i++)
        {
                // Keep removing top while the angle formed by points next-to-top,
                // top, and points[i] makes a non-left turn
                
                while (S.size() > 1 && orientation(nextToTop(S), S.top(), points[i]) !=2){
                        S.pop();
                }
                
                S.push(points[i]);
        }
        
        // Now stack has the output points, print contents of stack
        n = S.size();
        while (!S.empty()) {
                hull.push_back(S.top());
                S.pop();
        }
        return n;
}



int main()
{
        
        
        int T , n , p ;
        cin >> T;
        Point tmp;
        printf("%d\n",T);
        while (T -- ) {
                cin >> n;
                for (int i  = 0 ; i < n ; i ++ ) {
                        cin >> tmp.x >> tmp.y;
                        points.push_back(tmp);
                }
                //cin >> p   >> p;
                
                if(T) cin>>p;
                vector<Point> hull;
                int sz = convexHull( n , hull );
                cout << sz + 1 << endl;
                //cout << hull[sz -1 ].x << ' ' << hull[sz - 1].y << endl;
                for(int i = sz - 1; i >=0 ; i--)
                        cout << hull[i].x << ' ' << hull[i].y << endl;
                
                cout << hull[sz -1 ].x << ' ' << hull[sz - 1].y << endl;
                if(T) printf("-1\n");
                points.clear();
                
        }
        return 0;
        
}