Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
总是wrong answer,求指导以下是代码: #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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator