首页 > 代码库 > [COCI 2013/2014 ROUND 6] graskrizja

[COCI 2013/2014 ROUND 6] graskrizja

2024-08-10 09:30:03   217人阅读

分析：

　　这个题可以用分治的方法解决

　　先将所有的点按x坐标排序，以最中间的那个点的x坐标为轴，两边所有的点在轴上的对应的点加上，然后分别以同样的方法处理左右两个区间的点，递归处理下去知道区间只有一个点

下面是代码：

 1 #include<cstdio> 2 #include<algorithm> 3 #define maxn 50100 4 using namespace std; 5  6 class Point 7 { 8     public: 9         int x,y;10         void get(){scanf("%d%d",&x,&y);}11 };12 13 int n;14 Point s[maxn];15 16 bool cmp(Point a,Point b)17 {18     if (a.x<b.x) return 1;19     if (a.x>b.x) return 0;20     if (a.y<b.y) return 1;21     return 0;22 }23 24 void Add_Point(int a,int b)25 {26     if (a>=b) return;27     int mid=(a+b)>>1;28     Add_Point(a,mid-1);29     Add_Point(mid+1,b);30     for (int i=a;i<=b;i++) if (s[mid].y!=s[i].y)31         printf("%d %d\n",s[mid].x,s[i].y);32 }33 34 int main()35 {36     scanf("%d",&n);37     for (int i=1;i<=n;i++) s[i].get();38     sort(s+1,s+1+n,cmp);39     Add_Point(1,n);40     return 0;41 }

 

[COCI 2013/2014 ROUND 6] graskrizja


联系
我们