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

总是wrong answer,求指导

Posted by zhaochenyou at 2014-07-05 08:51:11 on Problem 1113
以下是代码:


#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <iomanip>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <cstdio>
#include <vector>
#include <limits>
#include <climits>
#include <list>
#include <memory>
using namespace std;
ifstream fin;

#define N_MAX 1200
#define PI 3.141592654
struct node{
	int x, y;
};
node ns[N_MAX];
node an[N_MAX];
int n, l;

double vec(node beg1, node end1, node beg2, node end2)
{
	int v1_x = end1.x - beg1.x;
	int v1_y = end1.y - beg1.y;
	int v2_x = end2.x - beg2.x;
	int v2_y = end2.y - beg2.y;
	return((double)v1_x * v2_y - v1_y * v2_x);
}

class compare2{
	node pp;
public:
	compare2(const node &cp): pp(cp){}
	bool operator()(node a, node b){
		double cross = vec(pp, a, pp, b);
		if(cross > 0)
			return(true);
		else if(cross == 0){
			int v1_x = a.x - pp.x;
			int v1_y = a.y - pp.y;	
			int v2_x = b.x - pp.x;
			int v2_y = b.y - pp.y;
			double dist_a = v1_x * v1_x + v1_y * v1_y;
			double dist_b = v2_x * v2_x + v2_y * v2_y;
			return(dist_a < dist_b);
		}
		return(false);
	}
};

double distan(node a, node b)
{
	double tmp = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
	return(sqrt(tmp));
}
void add_length(const vector<node> &ss);
void solve();
int main()
{
	//fin.open("main.in");
	//cin.rdbuf(fin.rdbuf());
	while(cin >> n >> l){
		memset(ns, 0, sizeof(ns));
		for(int i = 0; i < n; ++ i)
			cin >> ns[i].x >> ns[i].y;
		solve();
	}

    return 0;
}
void solve()
{
	int min_x = (~(1 << 31));
	int min_idx;
	for(int i = 0; i < n; ++ i){
		if(min_x > ns[i].x){
			min_x = ns[i].x;
			min_idx = i;
		}
		else if(min_x == ns[i].x && ns[i].y <= ns[min_idx].y){
			min_idx = i;
		}
	}
	swap(ns[n - 1], ns[min_idx]);

	node p0;
	p0.x = ns[n - 1].x; p0.y = ns[n - 1].y;
	sort(ns, ns + n - 1, compare2(p0));

	vector<node> stk;
	stk.push_back(p0);
	stk.push_back(p0);
	stk.push_back(ns[0]);
	stk.push_back(ns[1]);
	int index = 2;
	while(index < n){
		while(stk.size() >= 2 && vec(stk[(int)stk.size() - 2], ns[index],
					stk[(int)stk.size() - 2], stk[(int)stk.size() - 1]) >= 0)
			stk.pop_back();
		stk.push_back(ns[index]);
		++ index;
	}
	add_length(stk);
}
void add_length(const vector<node> &ss)
{
	double length = 0;
	for(int i = 1; i < (int)ss.size(); ++ i){
		if(i != (int)ss.size() - 1)
			length += distan(ss[i + 1], ss[i]);
		else
			length += distan(ss[0], ss[i]);
	}
	length += 2 * PI * l;

	printf("%.0f\n", length);
}

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