记录编号	154157	评测结果	AAAAAAAAAA
题目名称	[HAOI 2014]穿越封锁线	最终得分	100
用户昵称	wolf	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-03-21 19:23:23	内存使用	0.31 MiB

#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
#if defined wolf
const string ok="OK";
const string kk="	";
ofstream nnew("ha14b.in",ios::app);
ifstream fin("ha14b.in");
#define fout cout
#define Endl endl
#else
ifstream fin("ha14b.in");
ofstream fout("ha14b.out");
#endif
class node{
public:
	int x;
	int y;
	node(){
	}
	node(int a,int b){
		x=a;
		y=b;
	}
};
vector<node> TT;
multiset<double> rank;
set<double>::iterator it;
bool check(int b,int x){
	if(TT[b].x==x){
		if(TT[b-1].x>x&&TT[b+1].x>x||TT[b-1].x<x&&TT[b+1].x<x){
			return 1;
		}else{
			rank.insert(TT[b].y);
			return 1;
		}
	}else if(TT[b-1].x==x){
		return 1;
	}
	return 0;
}
void core(int i,int j,int x){//j=i-1
	/*cout<<"---------"<<endl;
	cout<<" i-->\t"<<TT[i].x<<kk<<TT[i].y<<endl;
	cout<<"i-1-->\t"<<TT[j].x<<kk<<TT[j].y<<endl;测试*/
	//////////////////////////////////////////////////////
	if(TT[i].x>=x&&TT[j].x<=x){// 从左到右
		goto begin;
	}else if(TT[i].x<=x&&TT[j].x>=x){//从右到左
		goto begin;
	}
	return;//无关的数据都舍弃
	begin:
	if(check(i,x)){//端点特判
		return;
	}
	if(TT[j].x==TT[i].x){//竖直线段
		rank.insert(TT[j].y);
		rank.insert(TT[i].y);
		return;
	}
	if(TT[j].y==TT[i].y){//横向线段
		rank.insert(TT[i].y);
		return;
	}
	//斜率 k
	double k=(TT[i].y-TT[j].y);
	k=k/(TT[i].x-TT[j].x);
	//  j = i-1
	if(TT[j].y<TT[i].y){//  k 大于 1 的线段
		double dx=x-TT[j].x;
		rank.insert(TT[j].y+fabs(double(k*dx)));
		//cout<<TT[j].y+fabs(double(k*dx))<<endl;
		return;
	}else if(TT[j].y>TT[i].y){//  k 小于 1 的线段
		double dx=x-TT[i].x;
		rank.insert(TT[i].y+fabs(double(k*dx)));
		//cout<<TT[i].y+fabs(double(k*dx))<<endl;
		return;
	}
}
void work(int x,int y,int h){//这个函数其实不用要
	for(int i=1;i!=TT.size()-1;++i){
		core(i,i-1,x);
	}
}
int analyse(){//对结果进行分析 两个点为一组
	double ans=0;
	it=rank.begin();
	while(it!=rank.end()){
		double a,b;
		a=*it;
		++it;
		b=*it;
		++it;
		ans+=b-a;
	}
	return int(ans);
}
int main(){
	int n;
	int maxy=0;
	fin>>n;
	for(int i=0;i!=n;++i){
		int a,b;
		fin>>a>>b;
		maxy=max(maxy,b);
		node u(a,b);
		TT.push_back(u);
	}
	TT.push_back(TT[0]);
	TT.push_back(TT[1]);
	int begx,begy;
	fin>>begx>>begy;
	work(begx,begy,maxy);
	fout<<analyse();
	//-------------------------*/
	#if defined wolf
	cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
	#endif
	return 0;
}
//Designed by wolf
//Fri Mar 20 2015