OJ Board

Code: Select all

#include<iostream>
#include<algorithm>
using namespace std;


class Point{

public:
int x,y;
void input(int a,int b);

};


void Point:: input(int a,int b)
{  x=a;
   y=b;

return ;
}

int cross(Point pi,Point pj,Point pk)
{  int a,b;
//cout<<"calling cross"<<endl;
    a=(pk.x-pi.x)*(pj.y-pi.y);
    b=(pj.x-pi.x)*(pk.y-pi.y);
    return a-b;

}

bool onsegment(Point pi,Point pj,Point pk)
{
    int minx=min(pi.x,pj.x),maxx=max(pi.x,pj.x),miny=min(pi.y,pj.y),maxy=max(pi.y,pj.y);

    if((minx<=pk.x) && (pk.x<=maxx) && (miny<=pk.y) && (pk.y<=maxy)) return true;
    //cout<<minx<<maxx<<maxy<<miny;
    //if(minx<=pk.x &(pk.x<=maxx) )return true;
    else return false;


}
bool intersect(Point P1,Point P2,Point P3,Point P4)
 {int d1,d2,d3,d4;
    d1=cross(P3,P4,P1);
    //cout<<"d1"<<d1<<endl;

    d2=cross(P3,P4,P2);
    //cout<<"d2"<<d2<<endl;

    d3=cross(P1,P2,P3);
    //cout<<"d3"<<d3<<endl;
    d4=cross(P1,P2,P4);
    //cout<<"d4"<<d4<<endl;
    if((d1>0&&d2<0 || (d1<0&&d2>0) )&& ((d3>0&&d4<0)||(d3<0&&d4>0))) return true;
    else if (d1==0 && onsegment(P3,P4,P1)) return true;
    else if(d2==0 && onsegment(P3,P4,P2))return true;
     else if(d3==0 && onsegment(P1,P2,P3))return true;
    else if(d4==0 &&onsegment(P1,P2,P4))return true;
    else return false;}


int main()
{  int tc,t=0;
cin>>tc;
    while(tc--){
    Point Ple,Pbe,P1,P2,P3,P4;
    int xle,yle,xbe,ybe,xleft,ytop,xright,ybottom;
    cin>>xle>>yle>>xbe>>ybe>>xleft>>ytop>>xright>>ybottom;

    Ple.input(xle,yle);
    Pbe.input(xbe,ybe);

     P1.input(xleft,ytop);
    P2.input(xleft,ybottom);
    P3.input(xright,ybottom);
    P4.input(xright,ytop);
   if(intersect(Ple,Pbe,P1,P2)==true)cout<<"T"<<endl;
   else if(intersect(Ple,Pbe,P2,P3)==true)cout<<"T"<<endl;
      else if (intersect(Ple,Pbe,P3,P4)==true)cout<<"T"<<endl;
   else if(intersect(Ple,Pbe,P4,P1)==true)cout<<"T"<<endl;
   else cout<<"F"<<endl;
   //cout<<"Case :"<<++t<<endl;
   }

    return 0;
}

Code: Select all

1
1 1 2 2 0 4 4 0

Code: Select all

T

Code: Select all

#include<iostream>
#include<complex>
using namespace std;

typedef complex<double> point;

#define vec(a,b) (b)-(a)
#define dot(a,b) (conj(a)*(b)).real()
#define cross(a,b) (conj(a)*(b)).imag()
#define lensqr(a) dot(a,a)
#define EPS 1e-9

double N, xstr, ystr, xend, yend, xtopLeft, ytopLeft, xbottomRight, ybottomRight;

bool Lines_intersect(const point &a, const point &b, const point &p, const point &q, point &ret) {
	double d1 = cross(vec(a,p),vec(a,b)),
			d2 = cross(vec(a,q),vec(a,b));
	ret = (d1 * q - d2 * p) / (d1 - d2);
	return fabs(d1 - d2) > EPS;
}

bool pointOnRay(const point &a, const point &b, const point &p) {
	return cross(vec(a,b),vec(a,p)) < EPS
			&& cross(vec(a,b),vec(a,p)) > -EPS
			&& dot(vec(a,b),vec(a,p)) > -EPS;
}

bool pointOnSegment(const point &a, const point &b, const point &p) {
	if (lensqr(vec(a,b)) < EPS)
		return lensqr(vec(a,p)) < EPS;
	return pointOnRay(a, b, p) && pointOnRay(b, a, p);
}

int main() {
	cin >> N;
	point ret;
	while (N--) {
		cin >> xstr >> ystr >> xend >> yend >> xtopLeft >> ytopLeft >> xbottomRight >> ybottomRight;

		if (Lines_intersect(point(xstr, ystr), point(xend, yend), point(xtopLeft, ytopLeft), point(xtopLeft, ybottomRight), ret)
				&& pointOnSegment(point(xstr, ystr), point(xend, yend), ret)
				&& pointOnSegment(point(xtopLeft, ytopLeft), point(xtopLeft, ybottomRight), ret)) {
			cout << "T" << endl;
			continue;
		}

		if (Lines_intersect(point(xstr, ystr), point(xend, yend), point(xtopLeft, ytopLeft), point(xbottomRight, ytopLeft), ret)
				&& pointOnSegment(point(xstr, ystr), point(xend, yend), ret)
				&& pointOnSegment(point(xtopLeft, ytopLeft), point(xbottomRight, ytopLeft), ret)) {
			cout << "T" << endl;
			continue;
		}

		if (Lines_intersect(point(xstr, ystr), point(xend, yend), point(xbottomRight, ytopLeft), point(xbottomRight, ybottomRight), ret)
				&& pointOnSegment(point(xstr, ystr), point(xend, yend), ret)
				&& pointOnSegment(point(xbottomRight, ytopLeft), point(xbottomRight, ybottomRight), ret)) {
			cout << "T" << endl;
			continue;
		}

		if (Lines_intersect(point(xstr, ystr), point(xend, yend), point(xtopLeft, ybottomRight), point(xbottomRight, ybottomRight), ret)
				&& pointOnSegment(point(xstr, ystr), point(xend, yend), ret)
				&& pointOnSegment(point(xtopLeft, ybottomRight), point(xbottomRight, ybottomRight), ret)) {
			cout << "T" << endl;
			continue;
		}

		if (xstr <= (xtopLeft > xbottomRight ? xtopLeft : xbottomRight)
				&& xstr >= (xtopLeft < xbottomRight ? xtopLeft : xbottomRight)
				&& ystr <= (ytopLeft > ybottomRight ? ytopLeft : ybottomRight)
				&& ystr >= (ytopLeft < ybottomRight ? ytopLeft : ybottomRight)) {
			cout << "T" << endl;
			continue;
		}
		cout << "F" << endl;
	}
	return 0;
}

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <climits>

#include <iostream>
#include<iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <sstream>
#include <algorithm>

using namespace std;

#define MAX 25
#define PI acos(-1.0)

typedef long long ll;
typedef pair <int, int> ii;
typedef vector <int> vi;
typedef vector <ii> vii;
typedef map <string, int> msi;

#define REP(i, b, e)\
    for(int i = int(b); i <= int(e); i++)
#define TRvi(c, it)\
    for(vi::iterator it = (c).begin(); it != (c).end(); ++it )
#define TRvii(c, it)\
    for(vii::iterator it = (c).begin(); it != (c).end(); ++it )
#define sf scanf
#define pf printf
#define si(x) sf("%d",&x)
#define in(x) cin>>x
#define out(x) cout<<(x)
#define ln length()
#define sz size()
#define clr clear()
#define pb push_back
#define mp make_pair
#define READ(f) freopen(f, "r", stdin)
#define mem(a,b) memset(a,b,sizeof(a))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define x first
#define y second

int area(ii p1, ii p2,ii p3)
{
    int res = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y);
    return (res == 0) ? 0 : (res > 0) ? 1 : -1;
}
bool onSigment(ii p1, ii p2,ii p3)
{
    return (p3.x >= min(p1.x, p2.x) && p3.x <= max(p1.x, p2.x) && p3.y >= min(p1.y, p2.y) && p3.y <= max(p1.y, p2.y));
}
bool isInside_rect(int xstart, int ystart, int xend, int yend,  int xleft, int ytop, int xright, int ybottom)
{
    return (xstart >= min(xleft, xright) && xstart <= max(xleft, xright) && ystart >= min(ybottom, ytop) && ystart <= max(ybottom, ytop) ||
    xend >= min(xleft, xright) && xend <= max(xleft, xright) && yend >= min(ybottom, ytop) && yend <= max(ybottom, ytop)
           );
}
bool isIntersect(ii lineA, ii lineB, ii rectX, ii rectY)
{
    int abx = area(lineA, lineB, rectX);
    int aby = area(lineA, lineB, rectY);

    int xya = area(rectX, rectY, lineA);
    int xyb = area(rectX, rectY, lineB);

    if(xya == 0 && onSigment(rectX, rectY, lineA) ||
        xyb == 0 && onSigment(rectX, rectY, lineB) ||
        abx == 0 && onSigment(lineA, lineB, rectX) ||
        aby == 0 && onSigment(lineA, lineB, rectY) ||
        xya * xyb < 0 && abx * aby < 0
       )
    return true;
    return false;
}

int main()
{
//    READ("input.txt");
    int n;
    int xstart, ystart, xend, yend, xleft, ytop, xright, ybottom;
    si(n);
    while(n--)
    {
        sf("%d %d %d %d %d %d %d %d", &xstart, &ystart, &xend, &yend, &xleft, &ytop, &xright, &ybottom);

        ii lineA = mp(xstart, ystart), lineB = mp(xend, yend);
        ii rectW = mp(xleft, ytop), rectX = mp(xright, ytop), rectY = mp(xright, ybottom), rectZ = mp(xleft, ybottom);

        if(isInside_rect(xstart, ystart, xend, yend, xleft, ytop, xright, ybottom))
        {
            pf("T\n");
            continue;
        }

        if(isIntersect(lineA, lineB, rectW, rectX) || isIntersect(lineA, lineB, rectX, rectY) ||
           isIntersect(lineA, lineB, rectY, rectZ) || isIntersect(lineA, lineB, rectZ, rectX))
            pf("T\n");
        else
            pf("F\n");
    }
    return 0;
}

Code: Select all

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;

int direction(int xi,int yi, int xj,int yj, int xk,int yk){
 return (xk-xi)*(yj-yi)-(xj-xi)*(yk-yi);
}

int intersect(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
    int d1,d2,d3,d4,x;
    d1=direction( x1, y1, x2, y2, x3, y3);
    d2=direction( x1, y1, x2, y2, x4, y4);
    d3=direction( x1, y1, x2, y2, x3, y4);
    d4=direction( x1, y1, x2, y2, x4, y3);

    if((d1>0&&d2>0&&d3>0&&d4>0)||(d1<0&&d2<0&&d3<0&&d4<0)) return 0;
    else {

        if(min(x3,x4)<=x1&&max(x3,x4)>=x1)
            {if(min(y3,y4)<=y2&&max(y3,y4)>=y2) return 1;}


        else if(min(x3,x4)<=x2&&max(x3,x4)>=x2)
             {if(min(y3,y4)<=y1&&max(y3,y4)>=y1) return 1;}
        else return 0;

    }
}

int main(){

    int t,x1,y1,x2,y2,rleft,rbottom,rright,rtop,check;
    
    scanf("%d",&t);

    while(t--){
        scanf("%d %d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&rleft,&rtop,&rright,&rbottom);
        check=intersect(x1,y1,x2,y2,rleft,rtop,rright,rbottom);
        if(check) printf("T\n");
        else printf("F\n");
    }
return 0;
}