Viewing Text Document

Title:

Owner: Andrian Kurniady

Last updated on: Tuesday, 15 July 2008

Description:

Content:

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;

bool isec(double x1, double y1, double x2, double y2, double x3, double y3,
              double x4, double y4, double &x, double &y){

    double nom = (x2-x1)*(y1-y3) + (y2-y1)*(x3-x1);
    double den = (x2-x1)*(y4-y3) - (x4-x3)*(y2-y1);
    
    if (den==0) return false;
    double a,b=nom/den;
    
    x=x3+(x4-x3)*b;
    y = y3 + (y4-y3)*b;
    if (x2-x1 == 0){
        a = (y-y1)/(y2-y1);
    } else {
        a = (x-x1)/(x2-x1);
    }
    return 0<=a && a<=1 && 0<=b && b<=1;
}

char buffer[100000];

int main(){
    int ntc;
    double PI = 2*acos(0);
    double PU = 2*PI;
    scanf("%d", &ntc);
    while (ntc--){
        int na;
        scanf("%d", &na);
        vector<pair<double,double> > polyA,polyB;
                
        gets(buffer);
        char *pos = strtok(buffer, " ");
        for (int i=0;i<na;i++){
            double x,y;
            sscanf(pos, "%lf", &x);
            pos = strtok(NULL, " ");
            sscanf(pos, "%lf", &y);
            pos = strtok(NULL, " ");
            polyA.push_back(make_pair(x,y));            
        }

        int nb;
        scanf("%d", &nb);
        gets(buffer);
        pos = strtok(buffer, " ");
        for (int i=0;i<nb;i++){
            double x,y;
            sscanf(pos, "%lf", &x);
            pos = strtok(NULL, " ");
            sscanf(pos, "%lf", &y);
            pos = strtok(NULL, " ");
            polyB.push_back(make_pair(x,y));            
        }
        double px,py;
        scanf("%lf%lf", &px,&py);
        
        vector<pair<double,pair<double,double> > > aAngles;
        vector<double > bAngles;
        
        for (int i=0;i<na;i++){
            double dx = polyA[i].first-px;
            double dy = polyA[i].second-py;
            aAngles.push_back(make_pair(atan2(dx,dy), make_pair(polyA[i].first, polyA[i].second)));
        }
        for (int i=0;i<nb;i++){
            double dx = polyB[i].first-px;
            double dy = polyB[i].second-py;
            bAngles.push_back(atan2(dx,dy));
        }
        sort(aAngles.begin(), aAngles.end());
        sort(bAngles.begin(), bAngles.end());
        
        pair<double,pair<double,double> > amin = aAngles[0];
        pair<double,pair<double,double> > amax = aAngles.back();
        
        double bmin = bAngles[0];
        double bmax = bAngles.back();
        
        double ad = amax.first-amin.first;
        double bd = bmax-bmin;
        if (ad>PI){
            swap(amin,amax);
            amin.first = amax.first-(PU-ad);
            ad = PU-ad;
        }
        if (bd>PI){
            swap(bmin,bmax);
            bmin = bmax-(PU-bd);
            bd = PU-bd;
        }
        
        while (amin.first<0){ amin.first+=PU; amax.first+=PU; }
        
        while (bmin<0){ bmin+=PU; bmax+=PU; }
        
        int intersect=0;
        for (double id=-5;id<=5;id+=1){
            double tbmin = bmin+id*PU;
            double tbmax = bmax+id*PU;
            
            tbmin>?=amin.first;
            tbmax<?=amax.first;

            if (tbmin<=tbmax){

                intersect=1;
                double secle = tbmax-tbmin;
                
                int kepotong=0;
                for (int i=0;i<nb;i++){
                    double sampah, sampahjuga;
                    if (isec(px,py,polyB[i].first, polyB[i].second,
                        amin.second.first, amin.second.second, amax.second.first, amax.second.second
                        ,sampah, sampahjuga) ){
                            
                        kepotong=1;
                        break;
                    }
                }                

                if (kepotong){
                    puts("CLEAR");
                } else {
                    if (secle+1e-9<ad){
                        puts("ALMOST CLEAR");
                    } else {
                        puts("NO VISION");
                    }
                }
                
                break;
            }
        }
        if (!intersect){
            puts("CLEAR");
        }
    }
    return 0;
}