답안 #380925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380925	2021-03-23T15:44:41 Z	fl0rian	Tri (CEOI09_tri)	C++14	10 / 100	2000 ms	5512 KB

tri

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000+10
#define rep(i,N) for(int i=0;i<N;i++)
#define TORAD  (180.0/3.141592653589793238463)
#define MARGERR -0.001
int N,K;

typedef struct point{
    int x;
    int y;
    double angle;

    point(int x1,int y1){
        x=x1;
        y=y1;
    }

    point(){
    }

    //pre : no points exactly on the line
    bool isover(point * b,point * a){
        //cout << "da ("<<a->x<<","<<a->y<<") " << "a ("<<b->x<<","<<b->y<<") \n";
        int v1[2] = {b->x - a->x, b->y - a->y};
        int v2[2] = {b->x - x, b->y - y};
        int xp = v1[0]*v2[1] - v1[1]*v2[0];
        return xp>0;
    }

    bool isunder(point * a,point * b){
        //cout << "da ("<<a->x<<","<<a->y<<") " << "a ("<<b->x<<","<<b->y<<") \n";

        if(x>b->x||y>a->y)return false;
        if(b->x == a->x || b->y == a->y) return true;

        int ox = a->x;
        int oy = b->y;

        double mx = b->x - a->x;
        double my = a->y - b->y;

        double distx = x-ox;
        double disty = y-oy;

        //cout << distx << " : " << disty << endl;

        double ratiox = distx/mx;
        double ratioy = disty/my;

        if(ratiox + ratioy + MARGERR > 1.0D)
            return false;
        return true;
    }

} * P;

point origin(0,0);

typedef struct triangle{

    point a;
    point b;

    bool isInside(point x){
        //cout << a.angle << " " << x.angle  << " " << b.angle <<endl;
        return x.angle<=a.angle && x.angle>=b.angle && x.isunder(&a,&b);
        //return x.isover(&origin,&b) && x.isunder(&origin,&a) && x.isunder(&a,&b);
    }

    bool insideTrigon(point s){
        int as_x = s.x-a.x;
        int as_y = s.y-a.y;
        bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0;
        if((origin.x-a.x)*as_y-(origin.y-a.y)*as_x > 0 == s_ab) return false;
        if((origin.x-b.x)*(s.y-b.y)-(origin.y-b.y)*(s.x-b.x) > 0 != s_ab) return false;
        return true;
    }

    triangle(){
    }

} * T;

vector<point> points(MAXN);
vector<triangle> triangles(MAXN);

bool solve(int t){
    rep(i,N)
        if(triangles[t].isInside(points[i]))
            return true;
    return false;
}

int mi22n(){

    point a(4,4);
    point b(6,3);

    cout << "da ("<<a.x<<","<<a.y<<") " << "a ("<<b.x<<","<<b.y<<") \n";

    point a3(8,3);

    if(a3.isover(&a,&b))
        cout<<"sopra";
    else
        cout<<"sotto";
}

int main(){

   // freopen("in2.txt","r",stdin);

    cin>>N>>K;

    rep(i,N){
        cin >> points[i].x>> points[i].y;
        points[i].angle = (atan2(points[i].x,-points[i].y)*TORAD)-90;
        //cout << "("<<points[i].x<<","<<points[i].y<<") = " << (atan2(points[i].x,-points[i].y)*TORAD)-90 << "°\n";
    }


    rep(i,K){
        int q,w,e,r;
        cin>>q>>w>>e>>r;
        double an1 = (atan2(q,-w)*TORAD)-90;
        double an2 = (atan2(e,-r)*TORAD)-90;
        //cout << "("<<q<<","<<w<<") = " << an1 << "°\n";
        //cout << "("<<e<<","<<r<<") = " << an2 << "°\n";

        if(an2<an1){
            triangles[i].a.x=q;
            triangles[i].a.y=w;
            triangles[i].b.x=e;
            triangles[i].b.y=r;
            triangles[i].a.angle=an1;
            triangles[i].b.angle=an2;
        }else{
            triangles[i].b.x=q;
            triangles[i].b.y=w;
            triangles[i].a.x=e;
            triangles[i].a.y=r;
            triangles[i].a.angle=an2;
            triangles[i].b.angle=an1;
        }

    }

    rep(i,K)
        cout<<(solve(i)?"Y":"N")<<"\n";

    return 0;
}

Compilation message

tri.cpp: In member function 'bool triangle::insideTrigon(point)':
tri.cpp:75:52: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   75 |         if((origin.x-a.x)*as_y-(origin.y-a.y)*as_x > 0 == s_ab) return false;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
tri.cpp:76:62: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
   76 |         if((origin.x-b.x)*(s.y-b.y)-(origin.y-b.y)*(s.x-b.x) > 0 != s_ab) return false;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
tri.cpp: In function 'int mi22n()':
tri.cpp:108:1: warning: no return statement in function returning non-void [-Wreturn-type]
  108 | }
      | ^

Subtask #1

10.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	508 KB	Output is correct
2	Incorrect	7 ms	364 KB	Output isn't correct
3	Incorrect	1472 ms	1920 KB	Output isn't correct
4	Execution timed out	2087 ms	2860 KB	Time limit exceeded
5	Execution timed out	2090 ms	5296 KB	Time limit exceeded
6	Execution timed out	2081 ms	4300 KB	Time limit exceeded
7	Execution timed out	2072 ms	5512 KB	Time limit exceeded
8	Execution timed out	2073 ms	4332 KB	Time limit exceeded
9	Execution timed out	2045 ms	4912 KB	Time limit exceeded
10	Execution timed out	2079 ms	5128 KB	Time limit exceeded