【UVA-1595】解题报告（STL,Vector）

原始题目

题目大意

给出平面上N个点，问是否可以找到一条竖线，使得所有点左右对称。

解题思路

纵坐标离散化后求每行得平均数，判断一下

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <vector>
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define cl(x,a) memset(x,a,sizeof(x))
#define all(x) x.begin(),x.end()
#define pb push_back
#define np next_permutation
#define mp make_pair
#define fi first
#define se second

#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int maxn=1e5+5;

const int maxl=26;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
vector<pii> v0;
vi v[1005];
double ans[1005];
bool cmp(pii a,pii b){
	if(a.first!=b.first) return a.first<b.first;
	else return a.second<b.second;
}
int t,n,a,b;
int main(){
	ios::sync_with_stdio(false);
	cin>>t;
		while(t--){
			rep(i,0,1005) v[i].clear();
			v0.clear();
			cin>>n;
			rep(i,0,n) {cin>>b>>a; v0.pb(mp(a,b));}
			sort(all(v0),cmp);
//			rep(i,0,n) 
//			{
//				cout<<v0[i].fi<<"  "<<v0[i].se<<endl;
//			}
			int temp=INF,cnt=-1,sum=0;
			rep(i,0,n){
				if(temp!=v0[i].first){
					if(cnt!=-1){
						ans[cnt]=(double)sum/v[cnt].size();
//						cout<<"ave["<<cnt<<"]="<<ans[cnt]<<endl;
					}
					temp=v0[i].first;
					cnt++;
					v[cnt].pb(v0[i].second);
					sum=v0[i].second;
				}
				else {v[cnt].pb(v0[i].second);sum+=v0[i].second;}
			}
			ans[cnt]=(double)sum/v[cnt].size();
		
			cnt++;
			int flag=1;
			rep(i,1,cnt){
//					cout<<"ave["<<i<<"]="<<ans[i]<<endl;
				if(abs(ans[i]-ans[i-1])>eps){
					flag=0;
					cout<<"NO"<<endl;
					break; 
				}	
			}
			if(flag) cout<<"YES"<<endl;
	}
}

收获与反思

  • 加快码速，秒之