OJ Board

Code: Select all

[cpp]

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct point 
{
    int x, y;
    point (int a=0, int b=0):x(a),y(b){}
    int operator*(const point &b)
	{
	    return x*b.y-y*b.x;
	}
    point operator-(const point &b)
	{
	    return point(x-b.x,y-b.y);
	}
};

int main()
{
    int k, n;
    cin>>k;
    cout<<k<<endl;
    while(k--)
    {
	vector<point> t;
	point s;
	cin>>n;
	for(int i=1; i<n; i++)
	{
	    cin>>s.x>>s.y;
	    t.push_back(point(s.x,s.y));
	}
	int wa;
	cin>>wa>>wa>>wa;
	int m=0;
	point mi=t[0];
	for(int i=1; i<t.size(); i++)
	{
	    if(t[i].y<mi.y)
	    {
		mi.x=t[i].x;
		mi.y=t[i].y;
		m=i;
	    }
	    else if(t[i].y==mi.y)
	    {
		if(t[i].x<mi.x)
		{
		    mi.x=t[i].x;
		    m=i;
		}
	    }
	}
	vector<point> z;
	for(int i=m; i<t.size(); i++)
	    z.push_back(t[i]);
	for(int i=0; i<m; i++)
	    z.push_back(t[i]);
	t=z;
	t.push_back(t[0]);
	stack<point> r;
	r.push(t[0]);
	r.push(t[1]);
	for(int i=2; i<t.size();)
	{
	    if(r.size()==1)
	    {
		r.push(t[i]);
		i++;
		continue;
	    }
	    point p=r.top(); r.pop();
	    point next=r.top(); r.push(p);
	    int val=((next-p)*(p-t[i]));
	    if(val>=0) // changed it to val>0 (still WA)
	    {
		r.push(t[i]);
		i++;
	    }
	    else
	    {
		r.pop();
	    }
	}
	vector<point> ans(r.size());
	while(!r.empty())
	{
	    ans[r.size()-1]=r.top();
	    r.pop();
	}
	cout<<ans.size()<<endl;
	for(int i=0; i<ans.size(); i++)
	    cout<<ans[i].x<<" "<<ans[i].y<<endl;
	if(k)
	    cout<<-1<<endl;
    }
    return 0;
}
[/cpp]

Code: Select all

// FINDING THE COMPLEX HULL USING GRAHM'S  SCAN 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <iterator>
#include <cstdlib>
#include <cmath>
#define EPS 0.0000001
#define PI pair < int ,int  >
using namespace std;

PI F;

double dist(PI A,PI B) {	// Returns squared distance
	return 1.0*(A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}

double sta(PI A,PI B,PI C) {
return 0.5*(A.first*B.second-A.second*B.first + A.second*C.first - A.first*C.second + B.first*C.second - C.first*B.second ) ;
}

class compare_angle {
		public:	
	bool operator() (PI A,PI B) {		
	if (fabs(sta(F,A,B))<EPS)
		if (dist(F,A)<dist(F,B)) return 1; else return 0;
	else
		if (sta(F,A,B)>EPS) return 1; else return 0;	
	}
};

class pair_compare {
	public:
	bool operator() (PI A,PI B) {
		if (A.second==B.second) return A.first<B.first;
		else return A.second<B.second;
	}		
};

void output(vector <PI> & Q) {
	Q.push_back(Q.front());	
	printf ("%d\n",Q.size());
	for (int i=0;i<Q.size();i++) 
		printf ("%d %d\n",Q[i].first,Q[i].second);
}

int main() {
	int test_cases,temp;
	scanf ("%d",&test_cases);
	printf ("%d\n",test_cases);
	for (int t=0;t<test_cases;t++) {
		vector < PI > V;
		vector < PI > hull;
		int N;
		if (t!=0) scanf ("%d",&temp);
		scanf ("%d",&N);
		V.resize(N);
		hull.resize(N);
		for (int i=0;i<N;i++) 
			scanf ("%d %d",&V[i].first,&V[i].second);
		// Sort and remove duplicates
		sort(V.begin(),V.end(),pair_compare());
		V.resize(distance(V.begin(),unique(V.begin(),V.end())));
		N=V.size();
		if (N<=4) {
			output(V);	
		} else {
			// Sort according to angle
			F=V[0];	
			vector < PI >::iterator VIT=V.begin();
			VIT++;
			sort(VIT,V.end(),compare_angle());
			V.push_back(F);
			hull[0]=V[0];
			hull[1]=V[1];
			int top=1,i=2;
			while (i<=N)
				if (sta(hull[top-1],hull[top],V[i])<EPS)
					top--;
				else {
					top++;
					hull[top]=V[i];
					i++;
				}		
			hull.resize(top);
			output(hull);	
			if (t!=test_cases-1) printf ("-1\n");
		}		
	}	
	return 0;
}