首页 > 代码库 > UVa1595，Symmetry

UVa1595，Symmetry

2024-07-13 19:23:25   215人阅读

这题居然是1A过的.....最近无比失落的心情顿时愉悦起来~

将数据全部读入

先用二维数据来存储坐标（先把题做出来再说= =）

题目中的x,y的坐标范围是-1W到1W....在数组下标里是不能用负数保存的（当然你偏用map当额没说= =），其实可以把x坐标左移1W个单位，这样最小坐标就从0开始了

然后随便找一行y（当然保证该行至少存在一点），那么可以确定这条竖线mid

枚举每一行，以mid为中点向两边扩展，每找到一对x1，x2，判断equal（mid-x1，x2-mid），若否，直接退出循环，输出NO。

2W*2W的数据啊，又大又慢，下面剪枝

1.其实y坐标是没用的，在枚举的时候大量的运算是无意义的，所有将y编号，读数据的时候，对应每一个新y，y=++ID；

2.对于x用vertor存储即可，v[ID].push_back(x);

0.062s过的，我以为还会超时呢，看样子数据大，但是数据量小啊。

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <vector>#include <algorithm>#include <cmath>#define maxn 20000+10#define c 10000using namespace std;vector<int> v[maxn];int N,a[maxn],cnt[maxn];double mid;int equal(double a,double b){    return fabs(a-b)>1e-6?0:1;}int main(){    int T,top=0;    cin>>T;    while (T-->0)    {        cin>>N;        top=0;        memset(a,0,sizeof(a));        memset(cnt,0,sizeof(cnt));        int x,y;        while(N-->0){            cin>>x>>y;            x+=c;            y+=c;            if (!a[y]) a[y]=++top;            v[a[y]].push_back(x);            cnt[a[y]]++;        }        for (int i=1;i<=top;i++)            sort(v[i].begin(),v[i].end());        mid=(v[1][cnt[1]-1]+v[1][0])/2.0;        int k,p,q,ok=1;        for (k=1;k<=top;k++)        {            p=0;            q=cnt[k]-1;            while (p<=q&&ok)                if (!equal(mid-v[k][p++],v[k][q--]-mid)) ok=0;            if (!ok) break;        }        if (ok) cout<<"YES"<<endl;else cout<<"NO"<<endl;        for (int i=1;i<=top;i++)            v[i].clear();    }}
View Code


联系
我们