随笔-141  评论-9  文章-3  trackbacks-0

之前做过CAD开发,对向量运算还是挺了解的,不过这题的边界情况害我wa了好多次。

Q1:求线段是否相交,两两枚举,注意重复,可以考虑跨立实验,需要改进的话,可以在跨立实验前加快速排斥实验。

Q2:设观察点为O,取线段AB,及AB中点C,连结AO、BO、CO;

1. 枚举所有线段,若AO、BO与同一条线段相交,则AB看不到。

2. 若A、B很近,则AB可以看成质点,AB看不到。

3. 枚举所有线段,分别与AO、BO、CO求是否相交,循环结束后判断是否有一条线段(AO、BO、CO)没有相交,如果有,则AB可以看见。


4. 二分AB, 对AC、BC进行上述过程。

ps :cross1是端点重合不算相交的运算,cross2是端点重合算相交的运算。

/*
ID: lorelei3
TASK: fence4
LANG: C++
*/


#include 
<fstream>
#include 
<iostream>
#include 
<cmath>

using namespace std;

struct Point{
    
double x,y;
}
;

struct Segment{
    Point start;
    Point end;
}
;

const double ZERO = 1e-5;

Point points[
205], ansb[205], anse[205], person;
int n, now;

inline 
double crossProduct(Point &p1, Point &p2, Point &p3){
    
return (p1.x-p3.x)*(p2.y-p3.y)-(p2.x-p3.x)*(p1.y-p3.y);
}


bool cross1(Point &p1, Point &p2, Point &p3, Point &p4){

    
//跨立实验
    if(crossProduct(p1, p4, p3)*crossProduct(p4, p2, p3)<=0return false;
    
if(crossProduct(p4, p2, p1)*crossProduct(p2, p3, p1)<=0return false;

    
return true;
}


bool cross2(Point &p1, Point &p2, Point &p3, Point &p4){

    
//跨立实验
    if(crossProduct(p1, p4, p3)*crossProduct(p4, p2, p3)<0return false;
    
if(crossProduct(p4, p2, p1)*crossProduct(p2, p3, p1)<0return false;

    
return true;
}


bool can(int k){
    
for(int i= k+1; i<n; ++i)
        
if(cross1(points[k], points[k+1], points[i], points[i+1]) )
            
return false;
    
return true;
}


bool same(Point &p1, Point &p2){
    
if(fabs(p1.x-p2.x)<=ZERO && fabs(p1.y-p2.y)<=ZERO )
        
return true;
    
return false;
}


bool check(Point &a, Point &b){

    
int i;

    
for(i=0; i<n; ++i)
        
if(i!=now && cross2(person, a, points[i], points[i+1]) && cross2(person,b, points[i], points[i+1]) )
            
return false;

    
bool b1=true, b2=true, b3=true;

    Point mid;
    mid.x 
= (a.x+b.x)/2;
    mid.y 
= (a.y+b.y)/2;

    
for(i=0; i<n; ++i){
        
if(i!=now){
            
if(b1&&cross2(a, person, points[i], points[i+1]))    b1=false;
            
if(b2&&cross2(b, person, points[i], points[i+1]))    b2=false;
            
if(b3&&cross2(mid, person, points[i], points[i+1]))    b3=false;
        }

    }


    
if(b1||b2||b3)    return true;
    
if(same(a,b))    return false;
    
if(check(a, mid)) return true;
    
if(check(mid, b)) return true;
    
return false;
}


int main(){

    
int i;

    ifstream fin(
"fence4.in");
    ofstream fout(
"fence4.out");

    fin
>>n;

    fin
>>person.x>>person.y;

    
for(i=0; i<n; ++i)
        fin
>>points[i].x>>points[i].y;
    points[n]
= points[0];

    
//Q1
    
    
for(i=0; i<n; ++i){
        
if(!can(i)){
            fout
<<"NOFENCE"<<endl;
            
return 0;
        }

    }

    

    
//Q2
    int cnt=0;
    
for(i=0; i<n-2++i){
        now 
= i;
        
if(check(points[i], points[i+1])){
            ansb[cnt]    
= points[i];
            anse[cnt]    
= points[i+1]; 
            cnt
++;
        }

    }

    
    now 
= n-1;
    
if(check(points[0], points[n-1])){
        ansb[cnt] 
= points[0];
        anse[cnt] 
= points[n-1];
        cnt
++;
    }


    now 
= n-2;
    
if(check(points[n-2], points[n-1])){
        ansb[cnt] 
= points[n-2];
        anse[cnt] 
= points[n-1];
        cnt
++;
    }




    fout
<<cnt<<endl;
    
for(i=0; i<cnt; ++i)
        fout
<<ansb[i].x<<" "<<ansb[i].y<<" "<<anse[i].x<<" "<<anse[i].y<<endl;

    
return 0;
}

posted on 2011-01-19 10:46 小阮 阅读(596) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理