Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

搞了一整天,过了,贴渣代妈(因为忘记删除调试信息WA了一次QAQ)

Posted by KatrineYang at 2016-07-08 09:42:53 on Problem 1066
//============================================================================
// Name        : main1066.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

class xianduan;
class jiaodian;
class quyu;

class zhixian{
public:

	int x_shi, y_shi, x_zhong, y_zhong;
	vector<int> jiaodians;
	void sortJD();
};

int xd_cnt = 0, jd_cnt = 0, qy_cnt = 0;
double trea_x, trea_y;

class xianduan{
public:
	int qidian;
	int zhongdian;
	int mian;
	bool bianjie;
	int fan;
	xianduan(): qidian(-1), zhongdian(-1), bianjie(false), fan(-1), mian(-1){}
};

class jiaodian{
public:
	double x;
	double y;
	vector<int> xianduans;
	jiaodian(): x(-1), y(-1){}
	jiaodian(double xx, double yy): x(xx), y(yy){}
};

class quyu{
public:
	vector<int> xianduans;
	bool chu;
	int depth;
	quyu(): chu(false), depth(0){}
};

xianduan xds[3000];
jiaodian jds[1500];
quyu qys[500];
zhixian zxs[35];

void zhixian::sortJD(){
		int gs = jiaodians.size();
		for(int i = 1; i < gs; i++){
			for(int j = i-1; j >= 0; j--){
				if(abs(jds[jiaodians[j]].x-x_shi) + abs(jds[jiaodians[j]].y-y_shi) < abs(jds[jiaodians[j+1]].x-x_shi) + abs(jds[jiaodians[j+1]].y-y_shi)){
					 break;
				}
				int temp = jiaodians[j+1];
				jiaodians[j+1] = jiaodians[j];
				jiaodians[j] = temp;
			}
		}
}


bool inRange(jiaodian jd){
	return jd.x > -1e-8 && jd.x < 100 + 1e-8 && jd.y > -1e-8 && jd.y < 100 + 1e-8;
}

jiaodian getJD(zhixian zx1, zhixian zx2){
	jiaodian temp(-1, -1);
	int x1 = zx1.x_shi, y1 = zx1.y_shi;
	int x2 = zx1.x_zhong, y2 = zx1.y_zhong;
	int x3 = zx2.x_shi, y3 = zx2.y_shi;
	int x4 = zx2.x_zhong, y4 = zx2.y_zhong;
	if((y2-y1)*(x4-x3)==(x2-x1)*(y4-y3)){
		return temp;
	}
	if(x1==x2){
		temp.x = x1*1.0;
		temp.y = y3 + (y4-y3) * (x1-x3) * 1.0 / (x4-x3);
		if(inRange(temp)) return temp;
		else return jiaodian(-1,-1);
	}
	if(x3==x4){
		temp.x = x3*1.0;
		temp.y = y1 + (y2-y1) * (x3-x1) * 1.0 / (x2-x1);
		if(inRange(temp)) return temp;
		else return jiaodian(-1,-1);
	}
	double k1 = (y2-y1)*1.0/(x2-x1), k2 = (y4-y3)*1.0/(x4-x3);
	temp.x = (k1*x1-k2*x3-y1+y3)/(k1-k2);
	temp.y = y1 + k1*(temp.x - x1);
	if(inRange(temp)) return temp;
	else return jiaodian(-1, -1);
}

bool you(xianduan& xd, jiaodian& jd){
	double x1 = jds[xd.qidian].x, x2 = jds[xd.zhongdian].x;
	double y1 = jds[xd.qidian].y, y2 = jds[xd.zhongdian].y;
	double x = jd.x, y = jd.y;
	return (x-x2)*(y2-y1)-(y-y2)*(x2-x1) > 1e-8;
}


int main() {
	int dian;
	cin >> dian;
	//int x_shi[35], y_shi[35], x_zhong[35], y_zhong[35];
	for(int i = 4; i < dian + 4; i++){
		cin >> zxs[i].x_shi >> zxs[i].y_shi >> zxs[i].x_zhong >> zxs[i].y_zhong;
	}
	cin >> trea_x >> trea_y;
	//cout << 1 << endl;
	zxs[0].x_shi = 100; zxs[0].x_zhong = 0; zxs[0].y_shi = 0; zxs[0].y_zhong = 0;
	zxs[1].x_shi = 0; zxs[1].x_zhong = 0; zxs[1].y_shi = 0; zxs[1].y_zhong = 100;
	zxs[2].x_shi = 0; zxs[2].x_zhong = 100; zxs[2].y_shi = 100; zxs[2].y_zhong = 100;
	zxs[3].x_shi = 100; zxs[3].x_zhong = 100; zxs[3].y_shi = 100; zxs[3].y_zhong = 0;
	for(int i = 1; i < dian+4; i++){
		for(int j = 0; j < i; j++){
			jiaodian temp = getJD(zxs[i], zxs[j]);
			//cout << temp.x << " " << temp.y << endl;
			if(temp.x != -1 && temp.y != -1){
				jds[jd_cnt] = temp;
				zxs[i].jiaodians.push_back(jd_cnt);
				zxs[j].jiaodians.push_back(jd_cnt);
				jd_cnt++;
			}
		}
	}
	//for(int i = 0; i < 4; i++) cout << zxs[i].jiaodians.size() << endl;
	for(int i = 0; i < dian+4; i++){
		zxs[i].sortJD();
		int num = zxs[i].jiaodians.size();
		for(int j = 0; j < num-1; j++){
			xds[xd_cnt].qidian = zxs[i].jiaodians[j];
			xds[xd_cnt].zhongdian = zxs[i].jiaodians[j+1];
			jds[zxs[i].jiaodians[j]].xianduans.push_back(xd_cnt);
			if(i < 4) xds[xd_cnt].bianjie = true;
			xd_cnt++;
			if(i >= 4){
				xds[xd_cnt].qidian = zxs[i].jiaodians[j+1];
				xds[xd_cnt].zhongdian = zxs[i].jiaodians[j];
				jds[zxs[i].jiaodians[j+1]].xianduans.push_back(xd_cnt);
				xds[xd_cnt].fan = xd_cnt-1;
				xds[xd_cnt-1].fan = xd_cnt;
				xd_cnt++;
			}
		}
	}
	//cout << xd_cnt << endl;
	/*
	for(int i = 0; i < jd_cnt; i++){
		cout << i << " " << jds[i].x << " " << jds[i].y << endl;
		for(int j = 0; j < jds[i].xianduans.size(); j++){
			cout << jds[i].xianduans[j] << " ";
		}
		cout << endl;
	}
	for(int i = 0; i < xd_cnt; i++){
		cout << i << " " << xds[i].qidian << " " << xds[i].zhongdian << endl;
	}
	*/
	bool state[3000] = {false};
	for(int i = 0; i < xd_cnt; i++){
		if(state[i]) continue;
		quyu tempq;
		tempq.xianduans.push_back(i);
		if(xds[i].bianjie) tempq.chu = true;
		xds[i].mian = qy_cnt;
		state[i] = true;
		int idx = i;
		//int cnt = 0;
		while(1){
			//cnt++;
			//cout << idx << endl;
			int jdidx = xds[idx].zhongdian;
			int len = jds[jdidx].xianduans.size();
			for(int j = 0; j < len; j++){
				if(you(xds[idx], jds[xds[jds[jdidx].xianduans[j]].zhongdian])){
					idx = jds[jdidx].xianduans[j];
					break;
				}
			}
			if(idx == i) break;
			tempq.xianduans.push_back(idx);
			if(xds[idx].bianjie) tempq.chu = true;
			xds[idx].mian = qy_cnt;
			state[idx] = true;
		}
		qys[qy_cnt] = tempq;
		qy_cnt++;
	}
	//cout << 1 << endl;
	jiaodian bao(trea_x, trea_y);
	int wz;
	/*
	cout << "qys" << endl;
	for(int i = 0; i < qy_cnt; i++){
		cout << i << ": " ;
		for(int j = 0; j < qys[i].xianduans.size(); j++){
			cout << qys[i].xianduans[j] << " ";
		}
		cout << endl;
	}
	*/
	for(int i = 0; i < qy_cnt; i++){
		int sz = qys[i].xianduans.size();
		bool OK = true;
		for(int j = 0; j < sz; j++){
			if(!you(xds[qys[i].xianduans[j]], bao)){
				OK = false;
				break;
			}
		}
		if(OK){
			wz = i;
			break;
		}
	}
	//cout << "weizhi: " << wz << endl;
	queue<int> qqy;
	for(int i = 0; i < qy_cnt; i++){
		if(qys[i].chu){
			qys[i].depth = 1;
			qqy.push(i);
		}
	}
	while(!qqy.empty()){
		int idxq = qqy.front();
		qqy.pop();
		int dpt = qys[idxq].depth;
		int geshu = qys[idxq].xianduans.size();
		for(int i = 0; i < geshu; i++){
			if(xds[qys[idxq].xianduans[i]].bianjie) continue;
			int fanmian = xds[xds[qys[idxq].xianduans[i]].fan].mian;
			if(qys[fanmian].depth != 0) continue;
			qys[fanmian].depth = dpt+1;
			qqy.push(fanmian);
		}
	}
	cout << "Number of doors = " << qys[wz].depth << endl;
	//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator