Re: 191 WA , plizzzzzzzzzzzz help me
Posted: Fri Mar 23, 2012 9:48 pm
Try the I/O posted in this thread.
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;
}
Please escape me from this evil situation.....I'm getting WA again and again but can't find where is the problem....help me please.
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, ¥d, &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;
}