Submission #2331812

---

Source Code Expand

#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstring>
#include<stack>
using namespace std;
#define EPS 1e-8
#define INF 1000000

struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x=_x; y=_y;
    }
    Point operator +(const Point p)const{
        return Point(x+p.x,y+p.y);
    }
    Point operator -(const Point p)const{
        return Point(x-p.x,y-p.y);
    }
    Point operator *(const double d)const{
        return Point(x*d,y*d);
    }
    bool operator <(const Point &p)const{
        if(x==p.x) return y<p.y;
        return x<p.x;
    }
	bool operator ==(const Point &p)const{
		return abs(x-p.x)<EPS && abs(y-p.y)<EPS;
	}
    double norm(){
        return x*x+y*y;
    }
	bool input(){
		if(cin>>x>>y) return true;
		return false;
	}
};

struct Line{
    Point a,b;
    Line(){}
    Line(Point _a,Point _b){
        a=_a; b=_b;
    }
	bool input(){
		if(a.input() && b.input()) return true;
		return false;
	}
};

struct Data{
	string s;
	Point p;
	Data(){}
	Data(string _s, Point _p)
	{
		s = _s; p = _p;
	}
	bool operator < (const Data &d) const{
		return p < d.p;
	}
};

typedef long long ll;
typedef Point Vector;
typedef vector<Point> Polygon;
typedef Line Segment;

double dot(Point p,Point q){
    return p.x*q.x+p.y*q.y;
}

double cross(Point p,Point q){
    return p.x*q.y-q.x*p.y;
}

int ccw(Point a,Point b,Point c){ //a,b,c,は全て異なる
	Vector v1 = b-a;
	Vector v2 = c-a;
    if(cross(v1,v2)>EPS) return +1; //a->b->c が反時計回り
    if(cross(v1,v2)<-EPS) return -1; //a->b->c が時計回り
	if(dot(v1,v2)<-EPS) return +2; //cがa-bより後ろ c<-a->b
	if(v2.norm()-v1.norm()>EPS) return -2; //cがa-bより前 a->b->c
    return 0; //cがa-b上 a->c->b
}

//多角形の点の内包
int contain_gp(Polygon g,Point p){
	Line l = Line(p,Point(INF,p.y));
	int cnt = 0, n = g.size();
	for(int i=0;i<n;i++){
		Vector a = g[i]-p;
		Vector b = g[(i+1)%n]-p;
		if(ccw(g[i],g[(i+1)%n],p)==0) return 1; //線分上
		if(a.y>b.y) swap(a,b);
		if(a.y<=EPS && EPS<b.y && cross(a,b)>EPS) cnt++;
	}
	if((cnt&1)==1) return 2; //内包している
	return 0; //内包していない
}

int main(){
	map<string, Point> latte;
	int N, M;
	string s;
	Point p;
	vector<Data> q;
	Polygon g;
	
	cin >> N;
	for(int i = 0; i < N; i++)
	{
		cin >> s;
		p.input();
		latte[s] = p;
	}
	cin >> M;
	for(int i = 0; i < M; i++)
	{
		cin >> s;
		g.push_back(latte[s]);
		latte.erase(s);
	}

	for(map<string, Point>::iterator itr = latte.begin(); itr != latte.end(); itr++)
	{
		if(contain_gp(g, itr->second) == 2)
		{
			q.push_back(Data(itr->first, itr->second));
		}
	}
	
	sort(q.begin(), q.end());

	for(int i = 0; i < q.size(); i++){
		cout << q[i].s << endl;
	}

	return 0;
}

Submission Info

Judge Result