Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

还是叉积。

Posted by dengyaolong at 2014-05-03 22:25:49 on Problem 3304
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
#define rc  1e-8
int N;
template<typename T>
class Point{
    public:
 T x;
 T y;
 Point(){};
 bool operator == (const Point &p)const{
      if(abs(x-p.x)<rc&&abs(y-p.y)<rc){
        return true;
      }
      return false;

  }
};
template<typename T>
class Line{
public:
    Line(){}
    void set(T l,T u,T r,T d){
      lu.x=l;lu.y=u;
      rd.x=r;rd.y=d;
    }


    Point<T> lu,rd;


};
vector<Line<double> > v(105);
template<typename T>
T mult(Point<T> &sp,Point<T> &ep,Point<T> &op){
  return (op.x-sp.x)*(sp.y-ep.y)-(op.y-sp.y)*(sp.x-ep.x);

}

template<typename T>
bool cross(Point<T> &p1,Point<T> &p2){
    if(p1==p2) return false;
    for(int i=0;i<N;i++){
        if(mult(p1,p2,v[i].lu)*mult(p1,p2,v[i].rd)>rc){
           return false;
        }
    }
    return true;
}
bool judge(int i,int j){
     if(cross(v[i].lu,v[j].lu))
         return true;
     if(cross(v[i].lu,v[j].rd))
         return true;
     if(cross(v[i].rd,v[j].lu))
         return true;
     if(cross(v[i].rd,v[j].rd))
         return true;
   return false;

}
bool solve(){
   if(N<3) return true;
   for(int i=0;i<N-1;i++)
     for(int j=i+1;j<N;j++)
        if(judge(i,j)){
            return true;
        }
   return false;
}
int main()
{
    int T;
    double l,d,r,u;
    int i;
    scanf("%d",&T);
    while(T--){

        scanf("%d",&N);
        for(i=0;i<N;i++){
            scanf("%lf%lf%lf%lf",&l,&u,&r,&d);
            v[i].set(l,u,r,d);
        }
        if(solve()){
          puts("Yes!");
        }else{
          puts("No!");

        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator