# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
380906 | fl0rian | Tri (CEOI09_tri) | C++14 | 2078 ms | 2984 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000+10
#define rep(i,N) for(int i=0;i<N;i++)
int N,K;
typedef struct point{
int x;
int y;
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){
return !isover(a,b);
}
} * P;
point origin(0,0);
typedef struct triangle{
point a;
point b;
bool isInside(point x){
return x.isover(&origin,&b) && x.isunder(&origin,&a) && x.isunder(&a,&b);
}
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;
//cout << "("<<points[i].x<<","<<points[i].y<<") = " <<atan2(points[i].x,-points[i].y) << "\n";
}
rep(i,K){
int q,w,e,r;
cin>>q>>w>>e>>r;
if(q<e){
triangles[i].a.x=q;
triangles[i].a.y=w;
triangles[i].b.x=e;
triangles[i].b.y=r;
}else{
triangles[i].b.x=q;
triangles[i].b.y=w;
triangles[i].a.x=e;
triangles[i].a.y=r;
}
}
rep(i,K)
cout<<(solve(i)?"Y":"N")<<"\n";
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |