Category Archives: Geometry

Convex Hull Algorithm

Aug 8

Posted by 

#include <iostream>
#include <complex>
#include <math.h>
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
typedef complex<double> point;

#define PI 3.141592653589793
#define EPS 0.0000000001
#define X real()
#define Y imag()
#define vec(a,b) ((b)-(a))
#define cross(a,b)  ((conj(a)*b).imag())
#define dot(a,b)  ((conj(a)*(b)).real())
#define length(a)  hypot((a).X,(a).Y)
#define lenSqr(a)  dot(a,a)
#define len(v) ((int)v.size)

point pivot(0,0);
bool collinear(point &a,point &b,point &c)
{
    return (fabs(cross(vec(a,b),vec(a,c))) < EPS);


}
bool ccw(point a,point b,point c)
{
    return cross(vec(a,b),vec(a,c)) > 0;
}
bool angleCmp(point a,point b)
{
    if(collinear(pivot,a,b))
    {
      return lenSqr(vec(pivot,a)) < lenSqr(vec(pivot,b));
    }
   return ccw(pivot,a,b);

}
vector<point> CH(vector<point> P)
{

    int i,N=(int)P.size();
    int po=0;
    for ( i=0;i<N-1;i++)
        if(P[i].Y < P[po].Y || (P[i].Y== P[po].Y && P[i].X < P[po].X))
            po=i;
    pivot = P[po];

    sort(P.begin(),P.end(),angleCmp);


    point prev(0,0),now(0,0);
    stack<point> S;
    S.push(pivot);
    i=1;
    while(i<N)
    {
        if(S.size()<2)
        {
            S.push(P[i++]);
        }
        else{
        now = S.top();
        S.pop();
        prev=S.top();
        S.push(now);
        if(ccw(prev,now,P[i]))
            S.push(P[i++]);
        else S.pop();
    }
    }

    vector<point> ConvexHull;
    ConvexHull.push_back(pivot);
    while(!S.empty())
    {

        ConvexHull.push_back(S.top());
        S.pop();
    }
    return ConvexHull;
}

Posted in Geometry

Leave a comment

3195. Doors and Penguins

Aug 7

Posted by

get 2 convex hull and then make a pointInsidePoly check

#include <iostream>
#include <complex>
#include <math.h>
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef complex<double> point;

#define PI 3.141592653589793
#define EPS 0.0000000001
#define X real()
#define Y imag()
#define vec(a,b) ((b)-(a))
#define cross(a,b)  ((conj(a)*b).imag())
#define dot(a,b)  ((conj(a)*b).real())
#define length(a)  hypot((a).X,(a).Y)
#define lenSqr(a)  dot(a,a)
#define len(v) ((int)v.size)
#define normalize(a)  (a)/(lenght(a))
point pivot(0,0);
bool collinear(point &a,point &b,point &c)
{
    return (fabs(cross(vec(a,b),vec(a,c))) < EPS);
}
bool angleCmp(point a,point b)
{
    if(collinear(pivot,a,b))
    {
      return lenSqr(vec(pivot,a)) < lenSqr(vec(pivot,b));
    }
   return (atan2(vec(pivot,a).Y,vec(pivot,a).X) - atan2(vec(pivot,b).Y,vec(pivot,b).X))<0;
}
bool ccw(point a,point b,point c)
{
    return cross(vec(a,b),vec(a,c)) >= 0;
}
bool myfunction (int i,int j) { return (i<j); }
vector<point> CH(vector<point> P)
{

    int i,N=(int)P.size();
    // return the vector
    if(N <=3){
    P.push_back(P[0]);
    return P;
    }
    int po=0;
    for ( i=0;i<N;i++)
        if(P[i].Y < P[po].Y || (P[i].Y== P[po].Y && P[i].X > P[po].X))
            po=i;
    point temp = P[0];
    P[0] = P[po];
    P[po]=temp;
    pivot = P[0];
    sort(++P.begin(),P.end(),angleCmp);

    point prev(0,0),now(0,0);
    stack<point> S;
    S.push(P[N-1]);
    S.push(P[0]);
    i=1;
    while(i<N)
    {

        now = S.top();
        S.pop();
        prev=S.top();
        S.push(now);
        if(ccw(prev,now,P[i]))
            S.push(P[i++]);
        else
        {
         S.pop();
    }
    }
    vector<point> ConvexHull;
    while(!S.empty())
    {

        ConvexHull.push_back(S.top());
        S.pop();
    }
    return ConvexHull;
}

double angle(point &a,point &b,point &c)
{
    double ux = b.X-a.X,uy =b.Y - a.Y;
    double vx = c.X-a.X,vy =c.Y - a.Y;
    return acos((ux*vx+uy*vy)/sqrt((ux*ux+uy*uy)*(vx*vx+vy*vy)));
}
bool inPolygon(point &p,vector<point> polygon)
{
    int n = (int)polygon.size();
    if(n==0)
    return false;
    double sum=0;
    for(int i=0;i<n-1;i++){
        point pp = polygon[i];
        point ppp= polygon[i+1];

        if(cross(vec(p,polygon[i]),vec(p,polygon[i+1])) <= 0)
            sum-=angle(p,polygon[i],polygon[i+1]);
        else sum+=angle(p,polygon[i],polygon[i+1]);
    }return fabs(sum-2*PI) < EPS || fabs(sum+2*PI) < EPS;

}

int main()
{
    int n,m;
    int t =1;
    while(scanf("%d %d",&n,&m)&&n!=0)
{
if(t!=1)
    printf("\n");
    vector<point> P1;
    int x1,x2,y1,y2;
    for(int i=0;i<n;i++)
    {
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        point p1(x1,y1);
        point p2(x2,y2);
        point p3(x1,y2);
        point p4(x2,y1);
        P1.push_back(p1);
        P1.push_back(p2);
        P1.push_back(p3);
        P1.push_back(p4);
    }
    vector<point> ans1;
    ans1 = CH(P1);
    vector<point> pp;
    bool check = true;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        point p1(x1,y1);
        point p2(x2,y2);
        point p3(x1,y2);
        point p4(x2,y1);
        pp.push_back(p1);
        pp.push_back(p2);
        pp.push_back(p3);
        pp.push_back(p4);
       if(inPolygon(p1,ans1) ||inPolygon(p2,ans1) ||inPolygon(p3,ans1) ||inPolygon(p4,ans1) )
            check = false;
    }
    vector<point> ans2;
    ans2 = CH(pp);
    for(int i=0;i<(int)ans1.size();i++)
    {
        point p = ans1[i];
       if(inPolygon(p,ans2) )
            check = false;
    }

    if(check)
    printf("Case %d: It is possible to separate the two groups of vendors.\n",t++);
    else printf("Case %d: It is not possible to separate the two groups of vendors.\n",t++);

}
    return 0;
}

Posted in Geometry, Must See, SPOJ

Leave a comment

Code Jam Beta 2008 Problem A. Triangle Trilemma

Aug 2

Posted by 

#include <iostream>
#include <complex>
#include <fstream>
#include <algorithm>
#include <cstdlib>

using namespace std;
typedef complex<double> point;
#define EPS 0.00000001
#define vec(a,b)  ((b)-(a))
#define cross(a,b) ((conj(a)*b).imag())
#define dot(a,b) ((conj(a)*b).real())
#define length(a)  dot(a,a)
bool pointOnRay(point &a,point &b,point &p)
{
    return fabs(cross(vec(a,b),vec(a,p)))<EPS;
}

bool pointOnSegment(point &a,point &b,point &p)
{
    if(length(vec(a,b))<EPS)
        return length(vec(a,p))<EPS;
    return pointOnRay(a,b,p)&&pointOnRay(b,a,p);
}
bool makeRight(point &a,point &b,point &c)
{
    return fabs(dot(vec(a,b),vec(a,c)))<EPS;
}
bool isIsos(point &a,point &b,point &c)
{
    return fabs(length(vec(a,b))-length(vec(a,c))) < EPS;
}
int main()
{
    int n,x1,x2,x3,y1,y2,y3;
    ifstream in ("A-large-practice.in");
    ofstream out ("A-large-practice.out");
    in >> n;
    for (int i=1;i<=n;i++)
    {
        in >> x1 >> y1 >>x2 >>y2 >>x3  >>y3  ;
        point a(x1,y1);
        point b(x2,y2);
        point c(x3,y3);
        bool ok = pointOnRay(a,b,c);
        if(ok==true)
        {
            out << "Case #" << i << ": not a triangle\n";
        }
        else{
        bool ok1 = isIsos(a,b,c)||isIsos(b,a,c)||isIsos(c,a,b);
        bool right = makeRight(a,b,c) || makeRight(b,a,c)||makeRight(c,a,b);
        bool acute = dot(vec(a,b),vec(a,c))>0 && dot(vec(b,a),vec(b,c))>0&&dot(vec(c,b),vec(c,a))>0;
        if (ok1) out << "Case #" << i <<": isosceles ";
        else out << "Case #" << i <<": scalene ";
        if(right)
        out<< "right triangle\n";
        else if(acute)
        out << "acute triangle\n";
        else out << "obtuse triangle\n";
        }
    }
    return 0;
}

Posted in Code Jam, Geometry, Must See

Leave a comment

SRM 550 DIV2 “RotatingBot” 550 problem

Jul 22

Posted by 

package SRM_550_DIV2;

import java.awt.geom.Line2D;

public class RotatingBot {
	public static int minArea(int[] moves) {
		int[][] lines = new int[moves.length][4];
		int dirc = 0;
		int x = 0;
		int y = 0;
		int minX = 0;
		int minY = 0;
		int maxX = 0;
		int maxY = 0;
		for (int i = 0; i < moves.length; i++) {
			if (dirc == 0) {
				lines[i][0] = x;
				lines[i][1] = y;
				lines[i][2] = x + moves[i];
				lines[i][3] = y;
				x = lines[i][2];

			} else if (dirc == 1) {
				lines[i][0] = x;
				lines[i][1] = y;
				lines[i][2] = x;
				lines[i][3] = y + moves[i];
				y = lines[i][3];
			} else if (dirc == 2) {
				lines[i][0] = x;
				lines[i][1] = y;
				lines[i][2] = x - moves[i];
				lines[i][3] = y;
				x = lines[i][2];
			} else if (dirc == 3) {
				lines[i][0] = x;
				lines[i][1] = y;
				lines[i][2] = x;
				lines[i][3] = y - moves[i];
				y = lines[i][3];

			}
			dirc++;
			dirc %= 4;
			minX = Math.min(minX, x);
			minY = Math.min(minY, y);
			maxX = Math.max(maxX, x);
			maxY = Math.max(maxY, y);
		}
		boolean check = true;
		for (int i = 0; i < lines.length && check; i++)
			for (int j = i + 2; j < lines.length && check; j++) {
				if (Line2D.linesIntersect(lines[i][0], lines[i][1],
						lines[i][2], lines[i][3], lines[j][0], lines[j][1],
						lines[j][2], lines[j][3])) {
					check = false;
				}
			}
		boolean[][] v = new boolean[maxY - minY + 1][maxX - minX + 1];
		int xx = Math.abs(0 - minX);
		int yy = Math.abs(0 - minY);
		for (int i = 0; i < lines.length; i++) {
			lines[i][0] += xx;
			lines[i][1] += yy;
			lines[i][2] += xx;
			lines[i][3] += yy;
		}

		int turn = 0;
		for (int i = 0; i < lines.length-1 && check; i++) {
			if (turn == 0) {
				for (int j = lines[i][0]; j <= lines[i][2]; j++)
					v[lines[i][1]][j] = true;
				if (lines[i][2] + 1 < v[0].length
						&& !v[lines[i][1]][lines[i][2] + 1])
					check = false;
			} else if (turn == 1) {
				for (int j = lines[i][1]; j <= lines[i][3]; j++)
					v[j][lines[i][0]] = true;
				if (lines[i][3] + 1 < v.length
						&& !v[lines[i][3] + 1][lines[i][0]])
					check = false;

			} else if (turn == 2) {
				for (int j = lines[i][0]; j >= lines[i][2]; j--)
					v[lines[i][1]][j] = true;
				if (lines[i][2] - 1 >= 0 && !v[lines[i][1]][lines[i][2] - 1])
					check = false;

			} else if (turn == 3) {
				for (int j = lines[i][1]; j >= lines[i][3]; j--)
					v[j][lines[i][0]] = true;
				if (lines[i][3] - 1 >= 0 && !v[lines[i][3] - 1][lines[i][0]])
					check = false;

			}
			turn++;
			turn %= 4;
		}
		if (!check)
			return -1;

		return (maxX - minX + 1) * (maxY - minY + 1);
	}

	public static void main(String[] args) {
		System.out.println(minArea(new int[] {5,4,5,3,3}));
	}

}

Posted in Geometry, Must See, Top Coder

Leave a comment

SRM 546 DIV 2 “TwoRectangles” 550 problem

Jun 16

Posted by

i used a boolean array and fill with true the celss which represents the first rectangle and then used a counter to count the number of intersections if zero then none if one then point else i use an if statement to check whether it is a segment or a rectangle 

package SRM_546_DIV_2;

public class TwoRectangles {
	public static String describeIntersection(int[] A, int[] B) {

		boolean[][] board = new boolean[1001][1001];
		for (int i = A[0]; i <= A[2]; i++)
			for (int j = A[1]; j <= A[3]; j++)
				board[i][j] = true;
		int count = 0;
		boolean flag = false;
		for (int i = B[0]; i <= B[2]; i++)
			for (int j = B[1]; j <= B[3]; j++) {
				if (board[i][j]) {
					count++;
				}
			}
		if (A[0] == B[2] || A[2] == B[0] || A[1] == B[3] || A[3] == B[1])
			flag = true;
		if (count == 0)
			return "none";
		else if (count == 1)
			return "point";
		else if (flag)
			return "segment";
		else
			return "rectangle";
	}

	public static void main(String[] args) {
		System.out.println(describeIntersection(
				new int[] { 28, 669, 700, 698 },
				new int[] { 28, 164, 700, 669 }));
	}
}

Posted in Algorithms, Geometry, Top Coder

Leave a comment