#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)
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<a->x || x >b->x || y>a->y || y<b->y)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("int.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:56:52: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
56 | if((origin.x-a.x)*as_y-(origin.y-a.y)*as_x > 0 == s_ab) return false;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
tri.cpp:57:62: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
57 | 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:89:1: warning: no return statement in function returning non-void [-Wreturn-type]
89 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
1006 ms |
1912 KB |
Output isn't correct |
| 4 |
Incorrect |
608 ms |
2796 KB |
Output isn't correct |
| 5 |
Incorrect |
1758 ms |
5544 KB |
Output isn't correct |
| 6 |
Execution timed out |
2075 ms |
4460 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2080 ms |
5496 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2096 ms |
4332 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2097 ms |
4732 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2094 ms |
5228 KB |
Time limit exceeded |
